Обзор

Когда мы пишем алгоритмы для решения проблем, можно найти более одного решения. В частности, в машинном обучении у нас есть разные алгоритмы, которые можно использовать для решения одной и той же проблемы машинного обучения. Например, для задач классификации мы можем использовать различные алгоритмы, такие как логистическая регрессия, SVM, деревья решений и т. Д. Сложность алгоритмов по времени и пространству может помочь выбрать правильный алгоритм для конкретной проблемы. Каждый алгоритм машинного обучения имеет свою временную и пространственную сложность. Прежде чем погрузиться в машинное обучение, мы должны получить вводную информацию об основах временной и пространственной сложности.

По сути, полнота программы показывает, сколько времени требуется программе на выполнение, а сложность пространства показывает, сколько места требуется для запуска программы. Чтобы понять основы сложности пространства и времени, давайте поработаем над кейсом.

Случай: найти, существует ли q (точка запроса) в списке размера n?

Линейный поиск

Допустим, наша точка запроса (q) равна 5, а размер списка (n) равен 15.

При выполнении линейного поиска для поиска точки запроса 5 в данном списке могут возникнуть три случая:

  1. Если 5 существует в списке с индексом k, программа выполняет k + 1 сравнения.
  2. Если 5 существует в списке с индексом (n - 1), программа выполняет n сравнений.
  3. Если 5 нет в списке, программа выполняет n сравнений.

Как видно, чтобы найти точку запроса, в худшем случае программе необходимо последовательно проверить все элементы списка (n сравнений). По мере увеличения размера списка количество сравнений будет пропорционально увеличиваться. Давайте покажем это практически на Python;

Сначала мы создаем перемешанный список:

# Imports
import numpy as np
import random 
# Create the shuffled List of numbers from 0 to 15
l = list(range(15))
random.shuffle(l)
# Display the shuffled list
l

Вот новый перемешанный список:

[12, 3, 4, 2, 14, 9, 11, 6, 1, 10, 0, 7, 13, 5, 8]

Напишем программу, которая выполняет линейный поиск, чтобы найти точку запроса из списка.

# Search for an element q in the list: O(n) where n is the length of the list
q = 5                       # 1 unit of time
isFound = False             # 1 unit of time
for x in l:                 # n times
    if x == q:                # 1 unit of time
        print('Found')        # 1 unit of time
        isFound == True       # 1 unit of time
        break                 # 1 unit of time
if isFound == False:        # 1 unit of time
    print('Not Found')      # 1 unit of time

Вывод:

Found

Я прокомментировал каждую строку программы, чтобы показать, сколько единиц времени потребовалось для выполнения каждой строки. Давайте посчитаем общее количество единиц времени, необходимое для работы нашей модели:

1 + 1 + n * (1 + 1 + 1 + 1) + 1+ 1 = 4n + 4 (n - размер списка)

Видно, что временная сложность нашей программы пропорциональна n, , поэтому временная сложность программы составляет порядок n (т.е. O (n)). Поскольку вы видите, что единицы времени и временная сложность - это не одно и то же, нам нужно выполнить некоторые преобразования. Главное, чтобы найти временную сложность, - это игнорировать константы из вычисленных единиц времени и выбрать самый высокий член, которому пропорционально время выполнения алгоритма. Вот несколько примеров:

При последовательном выполнении линейного поиска мы должны прочитать все элементы в списке один за другим и сравнить его с требуемым результатом. Поскольку нам не требуется никакого дополнительного места, кроме итератора, то есть x, нам требуется постоянное дополнительное пространство для линейного поиска, т.е. независимо от размера списка, нам требуется одна и та же память. Таким образом, пространственная сложность равна O (1).

Мы обнаружили, что наша программа имеет временную сложность O (n) и пространственную сложность O (1). В некоторых случаях существует компромисс между временной сложностью и пространственной сложностью. Допустим, в моей системе нет проблем с пространством, и мне нужно снизить временную сложность. Тогда как можно снизить временную сложность?

Бинарный поиск

Мы видели, что с программой, использующей линейный поиск, можно найти q (точку запроса) из списка размера n с временной сложностью O (n) и пространственной сложностью O (1). Временную сложность можно снизить до O (log (n)) с помощью двоичного поиска. Давайте посмотрим, как работает двоичный поиск.

Давайте еще раз посмотрим на перемешанный список:

[12, 3, 4, 2, 14, 9, 11, 6, 1, 10, 0, 7, 13, 5, 8]

Чтобы можно было выполнять двоичный поиск, наш список должен быть отсортирован. Тогда давайте отсортируем наш список на Python:

# Sort the list
l.sort()
# Display the sorted list
l

Новый отсортированный список:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

Пока программа выполняет двоичный поиск, она выполняет поиск в отсортированном списке, многократно разделяя интервал поиска на половину. Давайте посмотрим, как программа делит интервал поиска внутри, пока не найдет точку запроса.

[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]    # Before comparison
[0,1,2,3,4,5,6]                         # After 1st comparison
      [3,4,5,6]                         # After 2nd comparison
        [4,5,6]                         # After 3rd comparison
          [5,6]                         # After 4th comparison
          [5]                           # After 5th comparison

Чтобы разделить интервал поиска, программа вычисляет среднюю точку каждого интервала. После нахождения средней точки возможны три случая:

  1. Если точка запроса находится посередине, поиск завершается.
  2. Если точка запроса меньше средней точки, программа продолжает работу с левым подсписком.
  3. Если точка запроса выше средней точки, программа продолжает работу с правым подсписком.

Что ж, мы уже знаем, как программа работает внутри, теперь давайте посмотрим на саму рекурсивную программу:

# Import math library
import math
# Returns index of x in list if present, else -1
def binarySearch(list, l, r, x)
    # @list the sorted list
    # @l the left border
    # @r the right border
    # @x the query point
    # Check base case
    if r >= l:
        # Find the mid point
        mid = l + math.floor((r - l)/2)
        # If element is present at the middle itself
        if list[mid] == x:
            return mid
      
        # if element is smaller than mid, then it can only
        # be present in left sublist
        elif list[mid] > x:
            return binarySearch(list, l, mid-1, x)
        # Else the element can only be present in right sublist
        else:
            return binarySearch(list, mid+1, r, x)
    else:
        # Element is not present in the list
        # return -1
list = l
q = 5
# Call the function
binarySearch(list, 0, len(list)-1, q)

Программа обнаружила, что точка запроса находится в списке, поэтому вернула точку запроса:

5

Как видно, программа не проверяет все элементы списка, чтобы найти точку запроса, она просто делит интервал поиска на половину интервала, пока интервал не будет содержать только один элемент.

Теперь пора понять, как временная сложность уменьшается с O (n) до O (log (n)). Допустим, у нас есть список размера n. В первом цикле программа выполняет только 1 сравнение, и размер интервала поиска уменьшается до n / 2. При увеличении количества сравнений размер поискового интервала уменьшается. Давайте посмотрим на процесс:

Как видно, сравнения будут продолжаться до тех пор, пока в интервале поиска не останется только 1 (n / n) элемент. Затем давайте зададим вопросы, чтобы получить представление о таблице процессов. Если n = 8, сколько сравнений необходимо, чтобы найти точку запроса? Что делать, если размер списка 16?

Если n равно 8, программа выполнит 3 сравнения. Если размер равен 16, то количество сравнений увеличится только на одну единицу и будет 4. Есть ли связь? Да, существует логарифмическая связь. Когда программа делала линейный поиск, требовалось сделать n (размер списка) сравнений. Теперь потребуется выполнить сравнение log (n), когда программа выполняет двоичный поиск. Итак, мы видим, что временная сложность упала до O (log (n)), когда был применен двоичный поиск.

При использовании обоих методов поиска время выполнения программы составляло менее 1 секунды. В данном случае кажется, что мы не достигли такой большой разницы с помощью бинарного поиска, но мы не должны забывать, что это был лишь один из простейших примеров, объясняющих временную и пространственную сложность и показывающую возможность их уменьшения.