7

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

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

8
  • stackoverflow.com/a/487278/6104996 .... там кстати график наглядный 9 авг 2017 в 13:42
  • 1
    @АлексейШиманский, а у нас перевода не было?
    – Qwertiy
    9 авг 2017 в 14:15
  • @Qwertiy я не нашел. всё что я нашел примерное - это убитый старый вопрос ru.stackoverflow.com/q/64837/191482 от 11-го года 9 авг 2017 в 14:28
  • мне сделать ответ общим? Дописали бы. Если кто-то представляет что стоит писать)
    – pavel
    9 авг 2017 в 14:29
  • @pavel если возьмете на себя труд перевода, то репа ваша :).
    – andreycha
    9 авг 2017 в 14:29

1 ответ 1

15

O - ничего не означает. Просто буква :) Вообще это из теории эквивалентных функций https://habrastorage.org/getpro/habr/post_images/fd0/c1c/9ed/fd0c1c9ed7d949c2cd258b45302016ca.png

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

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

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

введите сюда описание изображения

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

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

введите сюда описание изображения

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

Ссылки:

1
  • и вот тут , можно весь цикл посмотреть , youtube.com/…
    – SergeyE
    9 авг 2017 в 15:45

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.