O(n²) - квадратичная сложность
Самый яркий пример квадратичной сложности - вложенный цикл.
Продолжаем тему пива 😋
На вечеринке 10 человек. Каждому необходимо выпить с каждым.
То есть первый человек обойдет всех, затем второй человек обойдет всех и т.д.
___
Вроде все понятно, но, наверное, вы скажете:
"Когда первый человек обойдет всех, он выпьет со вторым. Когда пойдет второй человек, он уже пил с первым, значит может не подходить…".
Вы снова абсолютно правы!
Для вычисления количества операций есть математическая формула:
n * (n - 1) / 2
Подставим значение:
10 * (10 - 1) / 2 = 45
Не смотря на то, что количество подходов будет даже меньше половины, асимптотика все равно остается O(n²).
Почему? Давайте разберемся...
Представьте эту запись n * (n - 1) / 2 как дробь:
n * (n - 1) - числитель
_________
2 - знаменатель
Вспоминаем фразу:
Сложность определяется самым быстро растущим элементом в выражении.
n - 1: Единицу можем откинуть, остается
n * n
_____
2
Запишем по-другому:
O(1/2n²) - коэффициенты можно убрать, остается O(n²).
Чувствуйте, как вы уже начинаете разбираться?
____
course_intro
