Страницы

Поиск по вопросам

воскресенье, 8 декабря 2019 г.

Что означает 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 полином может быть больше). Ссылки: английский связанный ответ цикл статей о О нотации, хабр примеры сложностей алгоритмов, хабр

Комментариев нет:

Отправить комментарий