Анализ сложности алгоритмов

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

Когда у вас возникает проблема с написанием кода, очень часто у проблемы есть несколько решений. Например, существует несколько разных способов сортировки списка. Когда проблему решают несколько алгоритмов, как вы узнаете, какой из них лучший? Этот самый простой? Самый быстрый? Самый короткий? Как мы анализируем алгоритмы и сравниваем их друг с другом?

Например, вам и вашему коллеге поручено написать функцию для суммирования чисел от 0 до N. Каждый из вас пишет по функции.

Список чисел:

n = [22, 10, 371, 50, 7, 92, 11, 12, 600, 3, 52]

Решение 1

def sum_numbers(n):
    num_sum = 0

for i in range(len(n)):
        num_sum += n[i]
    
    return num_sum

%timeit sum_numbers(n)

Решение 2

%timeit sum(numbers)

Как бы вы сравнили функции? Как бы вы узнали, какая из них лучше? Один из подходов заключается в измерении времени, необходимого для запуска, с помощью встроенной в Jupyter волшебной функции %timeit, чтобы сравнить время работы функций.

Решение 1

614 ns ± 22.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Решение 2

113 ns ± 2.65 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

Мы видим, что второе решение, использующее встроенную в Python функцию sum(), намного эффективнее. Запуск с гораздо большей скоростью, чем в первом случае, означает, что вторая функция намного эффективнее, но проблема в том, что мы не можем просто использовать время запуска в качестве объективного показателя, поскольку это будет зависеть от скорости работы самого компьютера и аппаратных возможностей. Мы хотим использовать объективное измерение того, сколько времени требуется для выполнения обеих функций, и хотим, чтобы оно не зависело от аппаратного обеспечения. И здесь на помощь приходят анализ сложности и обозначение Big O (или большая O).

Часто на собеседовании по программированию вас спросят, могли бы вы сделать лучше, найти более эффективное решение проблемы. Вот тут-то и вступает в игру сложность - то, что делает одно решение лучше другого, зависит от того, насколько оно сложнее.

Что такое сложность (complexity)? Это процесс определения эффективности алгоритма и объема ресурсов, используемых алгоритмом. Наиболее часто учитываемыми ресурсами являются время выполнения и использование памяти (сложность во времени и пространстве). Анализ сложности используется для выявления и предотвращения использования алгоритмов с длительным временем выполнения или высокой нагрузкой на память.

Временная сложность (Time complexity) - это показатель того, насколько быстро выполняется алгоритм.

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

Сложность алгоритма во время выполнения - это функция T(N), которая представляет количество операций за постоянное время, выполняемых алгоритмом на входных данных размера N.

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

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

Компьютеры обладают ограниченными ресурсами, такими как память, поэтому помимо учета временной сложности алгоритма, вам следует учитывать его использование. Пространственная сложность алгоритма - это функция, S(N), которая представляет количество блоков памяти фиксированного размера, используемых алгоритмом для ввода данных размером N, и включает в себя фиксированное пространство (память, необходимая вашей программе), пространство структуры данных (память, необходимая вашей программе для хранения набора данных), и временное пространство (для промежуточной обработки). Это также выражается с помощью нотации Big O.

Запись Big O - это математическая запись, которая описывает, как возрастают требования алгоритма к времени и пространству при увеличении размера N. Мы используем запись Big O для обобщения пространственно-временной сложности алгоритма в зависимости от размера его входных данных.

Использованные термины

• Алгоритм: последовательность шагов, которая решает проблему.
• Время выполнения: количество времени, которое требуется вашему компьютеру для выполнения алгоритма, написанного на языке программирования.
• Запись Big O: математическая запись, описывающая, как возрастают требования алгоритма к времени и пространству по мере увеличения размера N.
• Временная сложность: максимальное количество шагов, которое требуется алгоритму для выполнения при увеличении N.
• Пространственная сложность: объем памяти, необходимый алгоритму.
• Оптимальная сложность: как алгоритм работает при идеальных входных данных.
• Сложность в наихудшем случае: как алгоритм работает в наихудшем из возможных сценариев для него.