Что означает O(n^{2}). в описании сложности алгоритма?

#алгоритм #любой_язык #асимптотика

Что означает O(n2) в описании сложности алгоритма?

Что значит О, что значит n?
    

Ответы

Ответ 1

O - ничего не означает. Просто буква :) Вообще это из теории эквивалентных функций 

n - параметр размерности входных данных (обычно из контекста понятно о чём речь,
пример: размер массива). Или иной параметр, от значения которого зависит время работы. 

Теперь о вопросе что это значит в сумме, это значит что с ростом объёма входных данных
в 10 раз, ваша функция будет работать не более чем в 100 раз дольше. Учтите, оценки
асимптотические, работают при больших n. Поэтому иногда квадрат быстрее чем линия из-за
скрытых констант.

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



Следует помнить, что нотация обычно амортизирована и не всегда показывает время на
1 операцию. Пример - любой динамический массив вроде как и O(1) добавить, но регулярно
он может быть полностью скопирован (максимальное время единичной операции растёт, и
это не противоречит О - нотации).

Наглядный пример роста числа операций от О-нотации



При этом при О - нотации принято не указывать константы. Т.е. O(n) == O(2*n), так
же все младшие степени "поглощаются" старшими O(n2 + n) == O(n2). Исключение может
быть только при смешивании полиномиальной и экспоненциальной части (для малых n полином
может быть больше). 

Ссылки:


английский связанный ответ 
цикл статей о О нотации, хабр
примеры сложностей алгоритмов, хабр