Введение в нотацию Big O

Пространство и Время определяют любой физический объект во Вселенной. Точно так же сложность пространства и времени может определять эффективность алгоритма.

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

В этом посте вы найдете краткое введение во временную сложность алгоритма и как оценивать программу на основе временной сложности.

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

Сложность времени

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

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

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

Чтобы понять это, давайте воспользуемся примером: предположим, вы даете несортированный список [1, 7, 0, 9, 16, 3, 4] и вас просят найти индекс данного элемента в списке с помощью линейного поиска.

  • Наилучший случай. Наилучшим вариантом будет поиск первого значения в списке. В этом примере лучшим вариантом будет поиск значения 1. Поскольку это первое значение в списке, оно будет найдено в первой итерации.
  • Средний случай: средний случай - поиск элемента, присутствующего в середине списка. В этом примере средними случаями будет поиск значения 9. Так как это среднее значение в списке.
  • Наихудший случай. Наихудший случай - поиск элемента, присутствующего в самом конце списка. В этом примере наихудшим вариантом будет поиск значения 4. Поскольку это последнее значение в списке.

Почему важна эффективность

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

Предположим, в Интернете есть N рецептов, как испечь торт, и вы хотите найти лучший из них. Ваша поисковая система, Google, может использовать два разных алгоритма: один представляет собой алгоритм N-квадрата, а другой - алгоритм N * log (N) (где log - это двоичный логарифм).

Имея 100 000 релевантных сайтов, Google хочет отсортировать сайты в порядке убывания просмотров, которые получает каждый сайт.

  • N = 1,00,000

Предполагая, что на одно сравнение требуется 1 микросекунда, более быстрые алгоритмы (N * log (N)) сделают

(10⁵) * log (10⁵) ≈ 10⁵ * 16 сравнение, что составляет около 1,6 секунды.

неэффективному алгоритму потребуется 10⁵ * 10⁵ микросекунд, что составляет около 3 часов, что очень много!

Обозначение Big-O

На самом базовом уровне Big O или «асимптотическая» нотация предоставляет нам быстрый способ оценить производительность алгоритма.

Это способ понять, насколько масштабируемым является алгоритм. Он не сообщает вам, насколько быстро или медленно будет работать алгоритм, но вместо этого сообщает, как он изменяется в зависимости от размера входных данных.

Другими словами, это обозначение характеризует функции в соответствии с их темпами роста: разные функции с одинаковыми темпами роста могут быть представлены с использованием одной и той же нотации О.

Временные сложности

Постоянное время - O (1)

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

def add(x, y): 
  return x+y

Логарифмическое время - O (log n)

Говорят, что алгоритм имеет логарифмическую временную сложность, когда он уменьшает размер входных данных на каждом шаге.

Алгоритмы с логарифмической временной сложностью обычно встречаются при операциях с двоичными деревьями или при использовании двоичного поиска. Вот пример бинарного поиска.

Логарифмы

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

Логарифмы - это другой способ думать о силе или показателях

Например: 2¹⁰ = 1024

мы также можем выразить это как: log2 (1024) = 10

который читается как:

Основание логарифма 2 из 1024 равно 10.

Если вам нужно потратить немного больше времени, пытаясь понять логарифмы, я рекомендую Введение в логарифмы Академии Хана.

Линейное время - O (n)

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

Пример алгоритма линейного времени

Количество операций линейно увеличивается с размером ввода.

Квадратичное время - O (n²)

Алгоритм с эффективностью O (N²) увеличивается в удвоенной относительной скорости от O (N).

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

Квазилинейное время - O (n log (n))

Говорят, что алгоритм имеет квазилинейную временную сложность, когда каждая операция во входных данных имеет логарифмическую временную сложность. Это часто встречается в алгоритмах сортировки (например, сортировка слиянием, сортировка по времени, сортировка в кучу).

Сортировка слиянием

Реализация приведенной выше иллюстрации сортировки слиянием в Python.

Экспоненциальное время - O (2 ^ n)

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

Примером алгоритма экспоненциального времени является рекурсивное вычисление ряда Фибоначчи:

Более наглядный способ понять рекурсивный метод

Другой пример алгоритма O (2ᴺ) может быть использован для решения знаменитой головоломки Ханойская башня.

Дополнительная информация

Если вам интересно узнать больше, существует, например, класс крайне неэффективных алгоритмов с производительностью, которая снижается с факторной скоростью роста: один метод грубой силы для решения Задачи коммивояжера включает алгоритм O (N!), в то время как так называемый Bogosort имеет производительность O (logN!).