Теория сложности 101: Введение в Big O

Почему каждому специалисту по данным следует заботиться об алгоритмической сложности?

Один из важных терминов, с которыми вы столкнетесь как специалист по анализу данных или разработчик, - это «нотация большого O». нотация большого O - это нотация, используемая для выражения сложности любого компьютерного алгоритма с точки зрения времени и пространства. , Big O относится к тому, как алгоритм масштабируется относительно его входных данных.

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

Лучший и более эффективный способ проверить это поведение - использовать нотацию Big O. Если вы попадаете в науку о данных с технической подготовкой - изучали информатику, инженерию или любые смежные области - то вы, возможно, знакомы с нотацией Big O. Однако если вы переходите к науке о данных из нетехнической области, то нация Big O может показаться вам несколько сложной.

Хорошая новость в том, что даже те, у кого есть технический опыт, иногда находят Big O сбивающим с толку. Это не потому, что это сложно понять, а потому, что иногда применить это может быть непросто.

Эта статья предоставит простое введение в Big O и как вы можете управлять Big O вашего кода. Чтобы объяснить различные сложности, я буду использовать код Python. Однако такая же логика реализуема на любом другом языке программирования.

O(1)

Давайте начнем с простых вещей и будем двигаться дальше. Предположим, у нас есть некоторые записи данных, хранящиеся в форме списка - в C ++, Java и других языках это называется массивом - и я хочу получить 5-й элемент этого списка.

Это простая проблема для решения в Python; нам нужно получить доступ к 5-му адресу списка и прочитать его содержимое.

dataEntries = [53,71,40,11,23,10,-7,32]
print(dataEntries[4])

Для доступа к определенному адресу - индексу - в списке требуется O (1) - читается как порядок 1 - , что означает, что размер списка не имеет значения. Независимо от того, есть ли у него 7 записей или 1000000 записей, я просто перейду к ячейке 4, чтобы получить 5-й элемент.

Сложность O (1) - лучшая, она не всегда достижима, но если это так, то ваш код не зависит от размера ввода.

Другие операции со сложностью O (1) - это функция печати, простая арифметика - сложение, вычитание, умножение и деление в случае целых чисел. Умножение имеет тенденцию усложняться, когда речь идет о матрицах.

Функция ниже имеет сложность O (1). Если я хочу обобщить его, чтобы добавить / вычесть произвольное количество целых чисел, тогда сложность станет O (n).

def addSub2num(a,b,op):
   if op == "+":
     return a+b
   elif op == "-":
     return a-b
   else:
     print("invalid op")

O(n)

Коды, с которыми мы до сих пор работали, не включали никаких циклов или итераций. Там сложности имеют тенденцию к увеличению.

Возвращаясь к списку dataEntrie, вместо получения 5-го элемента я хочу распечатать все записи в списке. Для этого мне нужно будет использовать цикл. Это означает, что мне нужно будет повторить один и тот же процесс столько раз, сколько элементов у меня в списке. В нашем случае 8 раз.

dataEntries = [53,71,40,11,23,10,-7,32]
for i in dataEntries:
    print(i)

Сложность цикла зависит от того, сколько раз этот цикл запускается. Если у нас есть список из 5 элементов, цикл будет повторяться 5 раз; если у него 1000 элементов, мы будем повторять 1000 раз и так далее. Как вы могли заметить, в отличие от предыдущих примеров, этот код сильно зависит от размера ввода (dataEntries).

Чтобы представить это, мы предположим, что размер списка равен n, и поэтому сложность кода будет O (n). Другой пример - все элементы списка.

dataEntries = [53,71,40,11,23,10,-7,32]
sum = 0
for i in dataEntries:
   sum += i    
   print(sum)

Эту сложность часто называют линейной сложностью. Подумайте об этом так, поскольку взаимосвязь между размером и количеством итераций постоянна - может быть описана в терминах y = ax - тогда сложность будет линейной.

Итак, один цикл - O (n), что произойдет, если циклы вложены?

O(n²)

Если наш код содержит вложенные циклы, например, суммирование чисел в матричном - 2D-списке, поиск дубликатов в списке или практически любой код, в котором были вложенные циклы.

Давайте сосредоточимся на суммировании элементов двухмерного списка:

list2D = [[1, 2],[3, 4]]
sum = 0
for row in range (len(list2D)):
        for col in range(len(list2D[0])):
            sum = sum + input[row][col]

Поскольку каждый цикл имеет сложность O (2) и они вложены, мы умножаем их сложность и получаем O (4). Это O (n²).

Важно отметить, что, вычисляя сложность, мы пытаемся выяснить наихудший сценарий. Для матрицы время, необходимое для сложения, определяется полиномом an²+bn+c. Вот почему O (n²) называется полиномиальной сложностью.

O (журнал (п))

Прежде чем мы перейдем к объяснению, здесь log log с основанием 2, а не с тем, как он используется в математике, который представляет собой log с основанием 10.

Например, предположим, что мы хотим просуммировать четные числа от 1 до определенного верхнего предела n. Тогда мы могли бы сделать что-то вроде этого:

i = 1
sum = 0
n = 100
while(i < n):
    i = i * 2
    sum += i

Разница в том, что наш цикл пропускает некоторые числа и запускается только log (n) раз. Следовательно, сложность здесь становится O (log (n)).

Сложность O (log (n)) часто является сложностью большинства алгоритмов типа «разделяй и согласовывай», таких как двоичный поиск, сбалансированные двоичные деревья поиска, многие рекурсивные алгоритмы и очереди с приоритетом.

O (п журнал (п))

Если у нас есть код или алгоритм со сложностью O (log (n)), который повторяется несколько раз, то он становится O (n log (n)). Известными примерами этого являются сортировка слиянием и быстрая сортировка.

Правила Big O

Просматривая приведенные выше примеры, вы, возможно, выяснили некоторые правила вычисления Big O, но давайте подведем их итог:

1. Чтение, запись элемента в списке или словаре имеет O (1).
2. Выполнить итерацию можно за O (n).
3. Вложенные циклы приводят к сложности O (n²).
4. Любой подход «разделяй и согласовывай» или циклы, обрабатывающие двоичные числа, имеют сложность O (n log (n)).
5. Суммируем сложность последовательных циклов и умножаем сложность вложенных циклов.

Выводы

Хотя большая часть внимания уделяется сбору, чтению и анализу данных в области науки о данных, удобство работы с временными и пространственными сложностями (Big O) может вывести ваш набор навыков на новый уровень.

Я считаю, что каждый специалист по данным должен знать основы нотации Big O. Знание того, как алгоритм, который вы выбрали для реализации приложения, ведет себя с разными размерами и формами входных наборов данных, может сделать или сломать ваш проект.

Любой программист может решить проблему за достаточно времени, но решив ее хорошо - это то, что мы хотим сделать! - Роб Конери

Некоторые алгоритмы отлично работают с небольшими наборами данных, но не справляются с большими наборами данных. Обозначение Big O представляет собой простой способ для специалистов по обработке данных узнать, чего ожидать от алгоритма и как его эффективно использовать.

Основы Big O довольно просты и понятны, поэтому изучить их будет намного проще, чем изучить другие аспекты науки о данных. Однако для его овладения потребуется много практики. С другой стороны, как специалист по данным, вы создаете множество проектов, что дает много шансов отточить свои навыки Big O.