Понятие «O» большого. Временная сложность.

При анализе сложности алгоритмов обычно используется понятие «O» большое. Пришло время узнать, что это такое.
Допустим, вы хотите найти максимум двух различных чисел. Сколько для этого нужно элементарных операций? Всего одна: сравнить два числа — большее и есть максимум.
А сколько нужно операций, чтобы найти максимум трёх разных чисел? Две: сначала ищем максимум первых двух чисел, потом сравниваем его с третьим числом. Ответом будет наибольшее. Аналогично для нахождения максимума из четырёх чисел потребуется три операции.
Легко заметить закономерность: чтобы найти максимум из n чисел, нужно выполнить n - 1 элементарную операцию.
Насколько изменится вычислительная сложность алгоритма при увеличении объёма входных данных? Если добавить одно число, количество сравнений увеличивается на единицу. Какая функциональная зависимость описывает эту закономерность?
Обозначим количество чисел за n, а количество элементарных операций, которые нужно выполнить для нахождения максимума — за T. Получаем, T = n - 1. Это уже знакомая вам линейная зависимость.
Уравнение линейной зависимости y = kx + b — как раз наш случай при k = 1 и b = -1. Алгоритм нахождения максимума имеет линейную сложность.
image
Говорят, что линейный алгоритм имеет сложность O(n). Простыми словами это означает, что количество элементарных операций в этом алгоритме будет пропорционально n, где n — размер входных данных. Слагаемое минус единицу при оценке не учитывают. Так поступают со всеми константными слагаемыми, потому что они не меняются при росте n, и нет возможности на них повлиять.
Если количество элементарных операций не зависит от объема входных данных, говорят, что сложность алгоритма равна O(1).
Рассмотрим ещё один пример. Вы собираетесь праздновать новый год со своими друзьями. Допустим, их m человек. Каждому другу надо придумать подарок, и вы хотите обсудить идеи с остальными участниками праздника. Для этого создаёте в любимом мессенджере чат про каждого из друзей, добавляя в него всех, кроме обсуждаемого человека. Какая будет сложность алгоритма, если за элементарную операцию считать добавление человека в чат?
Всего друзей m, значит будет создано m чатов. В каждый из чатов нужно добавить m - 1 человек (вы добавляетесь в чат автоматически при создании), то есть всего получится m(m - 1) операций. Вычислительная сложность алгоритма выражается соотношением T(m) = m² - m. На языке O-нотации скажем: алгоритм имеет сложность O(m²) (произносится как «О от эм в квадрате»). То есть количество элементарных операций будет пропорционально m². Почему мы выкинули - m? Потому что функция y = m² растёт гораздо быстрее, чем y = m, и при больших входных данных зависимость будет выглядеть, как квадратичная.
Как думаете, зачем нужна приблизительная оценка в О-нотации, если можно посчитать точную вычислительную сложность?
2 из 3 правильно и 1 неправильно
Наверное вы заметили, что мы довольно свободно выбрасываем слагаемые из T(n), чтобы получить оценку O(n). Разберёмся, что можно выкидывать, а что нельзя. Предположим, для какого-то алгоритма мы получили оценку T(n) = 18n³ + 153n - 78.
Как думаете, какая сложность у этого алгоритма?
3 из 5 правильно и 2 неправильно
Поскольку нам интересно то, на какую функцию больше всего похожа зависимость T(n), мы можем выкинуть все слагаемые кроме старшего по степени. Также можно выбросить коэффициент при самом старшем слагаемом. Ведь важна лишь скорость роста функции. Нет разницы между 3n³ и 789n³, зависимость всё равно кубическая.
Потренируемся определять сложность алгоритмов.
Рита придумала алгоритм и записала зависимость количества элементарных операций от размера входных данных, получилось T(n) = 3 × n⁴ + n². Какова сложность алгоритма?
Каждый день Гоша выбирает, что надеть, запуская программу на компьютере. Алгоритм перебирает все сочетания штанов и футболок, показывает их Гоше, и просит оценить сочетание по шкале от 1 до 10. После этого программа просматривает все оценки, выбирает максимальную и говорит Гоше, что надеть. У Гоши n штанов и m футболок. Какова сложность алгоритма?
Алла написала алгоритм поиска нужного бутика среди всех n магазинов города. Магазины в списке лежат в алфавитном порядке. Алгоритм Аллы работает так: смотрит в середину списка магазинов, сравнивает название с искомым. Если название бутика по алфавиту раньше, то переходит к первой половине списка и делает то же самое, и так пока не останется одно название. Какова сложность алгоритма?
Есть два алгоритма, один работает за O(n), а другой за O(n²). Какой стоит выбрать, чтобы скорость была лучше?
Гоша оценил сложность своего алгоритма как O(n²). Тимофей решил ту же задачу за O(nlogn). Гоша не понимает, это лучше или хуже, чем у него?
В этом уроке вы познакомились с О-нотацией, в следующем уроке вас ждут более строгие определение, связанные с этим понятием. Не пугайтесь формул, они описывают то же самое, о чем мы только что говорили.