Нотация Big O используется для описания производительности алгоритма, в частности, она отвечает на вопрос: как увеличивается время выполнения функции по мере увеличения размера входных данных?
Для наших целей мы можем думать об алгоритме как о функции. **Производительность определяется размером входных данных.** Это чрезвычайно важно знать. Например, предположим, что входной размер представляет собой длину массива. Ухудшается ли производительность, если размер ввода увеличивается? Или производительность остается неизменной, независимо от того, имеет ли размер ввода длину 3 по сравнению с массивом длиной 1000?
Временная сложность (количество шагов) описывает время, необходимое для запуска алгоритма. Но важно отметить, что на самом деле это не мера времени. Время здесь оценивается количеством шагов/операций, которые выполняет алгоритм.
O(n)-линейная временная сложность
Количество шагов для выполнения алгоритма прямо пропорционально размеру входных данных. Например,
В массиве 4 элемента (входной размер здесь n = 4). Эта функция выполняет всего 4 шага.
Пример из жизни: допустим, вы ищете розовую блузку в небольшом универмаге. Начиная с конца вешалки, вы просматриваете каждый отдельный предмет одежды, пока не найдете розовую блузку, которую искали. Если вы перебрали 25 предметов одежды, прежде чем нашли розовую блузку, входными данными будет 25 предметов одежды, а количество операций (просмотр одежды) также будет равно 25 шагам. Однако, если вы решите, что выбора недостаточно, вы решите пойти в более крупный универмаг. На этот раз вы просматриваете 100 предметов одежды, прежде чем найдете то, что ищете. В данном случае на входе 100 предметов одежды, а количество операций 100.
Пример структуры данных: массив
O(n2)-квадратичная временная сложность
Количество шагов для выполнения алгоритма равно квадрату входного размера.
Пример из реальной жизни: допустим, вы и двое ваших друзей пришли на дегустацию вин. Винный хозяин вынес на дегустацию 3 самых дорогих вина. Конечно, каждый человек хочет попробовать все вино. Таким образом, когда человек А пробует вино1, вино2 и вино3, это в общей сложности 3 шага. Когда человек Б пробует вино1, вино2 и вино3, это в общей сложности 3 шага. Человек C пробует вино1, вино2 и вино2, всего 3 шага. Всего было предпринято 9 шагов, чтобы все попробовали все вино.
Пример структуры данных: пузырьковая сортировка
O(1)-постоянная временная сложность
Количество шагов для выполнения алгоритма не зависит от размера входных данных (n). Количество шагов остается постоянным по мере увеличения размера ввода.
Пример из жизни: допустим, у вас есть автомат по производству жевательных резинок, в котором есть 200 шариков жевательной резинки (n = 200). Если вы хотите шарик резинки, вы 1) положите четвертак и 2) получите шарик резинки (количество шагов = 2). У тебя также есть подлый младший брат, который вынул большую часть шариков жвачки, так что теперь в автомате осталось только 5 шариков жевательной резинки. Несмотря на то, что машина имеет 200 против 5, вы все равно получаете только 1 шарик жевательной резинки, когда кладете четвертак. Вам все еще нужно сделать 2 шага, чтобы получить шарик жвачки.
n = 200 шариков резинки, количество шагов для получения шарика резинки = 2
n = 5 шариков резинки, количество шагов для получения шарика резинки = 2
Пример структуры данных: хеш-таблица
O(log n)-логарифмическая временная сложность
Количество шагов для выполнения алгоритма пропорционально логарифму размера входных данных.
Давайте подумаем, как работают логарифмы.
Вы видите закономерность? Поскольку размер ввода увеличивается экспоненциально, количество шагов увеличивается один за другим.
Пример из реальной жизни:
a b c d e f g h I j k i m n o p q r s t u v w x y z
Допустим, вы хотите найти в словаре определение слова «щенок». Вы не будете начинать с начала словаря (линейная временная сложность) для поиска «щенка», потому что это займет вечность. Однако вы можете начать с середины словаря, что приведет вас к разделу «М» по алфавиту. Поскольку вы знаете, что буква «р» стоит после «м», вы можете отбросить все, что стоит перед «м».
m n o p q r s t u v w x y z
Теперь вы можете искать в словаре от буквы «м» до «з». В этот момент вы можете перейти на полпути и, вероятно, окажетесь на букве «t». Вы знаете, что «p» предшествует «t», поэтому вы можете отбросить все, что следует после «t».
m n o p q r s t
Если вы дойдете до середины, вы окажетесь на «p», и вам потребуется еще несколько шагов, чтобы добраться до «щенка».
Это похоже на то, о чем мы говорили ранее, когда рассматривали закономерности логарифмов. Хотя размер ввода огромен (все страницы словаря), вам потребовалось всего 3 попытки (количество шагов = 3), чтобы добраться до буквы «p»! Представьте себе разницу между необходимостью просматривать каждую страницу с самого начала (линейная временная сложность), которая потребовала бы перелистывания страницы более 1000 раз, и перелистыванием страницы всего несколько раз.
Пример структуры данных: бинарное дерево поиска
