7

Просьба, если в ответе решите использовать высшую математику, переведите сразу на обыденный язык, чтобы все было понятно и не возникло новых вопросов.

6
  • Stack Overflow на русском — это сайт вопросов и ответов для профессиональных разработчиков программного обеспечения, энтузиастов программирования и системных администраторов. Сайт создан и управляется сообществом. - вопрос в заголовке более чем уместен, @Harry
    – Kromster
    23 фев в 8:51
  • @Kromster В результате в вопросе нет вопроса. Тогда логично вообще убрать требование к телу вопроса, и разрешить задавать вопросы, состоящие только из заголовка.
    – Harry
    23 фев в 9:02
  • 1
    Не уверен в корректности с математической точки зрения, но o-малое выглядит более строгим требованием, чем O-большое, что влечёт трудности с практическим применением. Когда говорят, имеет сложность O(N^2), то подразумевается, что сложность действительно может быть квадратичной. Когда говорят имеет сложность o(N^2), то имеется ввиду, что сложность будет гарантированно лучше, чем квадратичная. Например для линейного поиска в массиве можно сказать, что он имеет сложность O(N), но нельзя сказать o(N). Можно сказать, что он имеет сложность o(N * log(N)), но это сбивает с толку.
    – wololo
    23 фев в 9:15
  • 1
    Иными словами, O-большое сразу наглядно демонстрирует худший случай, а o-малое показывает некоторую недостижимую границу, и не совсем очевидно, что на самом деле представляет из себя худший случай.
    – wololo
    23 фев в 9:42
  • 1
    Ну и o-малое тоже используется при оценки алгоритмов. Хороший пример — это коллекции Map и Set в javascript. Спецификация языка требует, чтобы время доступа к элементу коллекции в среднем было сублинейным (24.1 Map Objects), т.е. в среднем имело сложность o(n). В терминах O-большого это может быть сложность,например, O(1), или O(log(n)), или даже O(sqrt(n)).
    – wololo
    23 фев в 10:22

2 ответа 2

4

O-большое - аналог нестрогого неравенства (≤),
o-малое - аналог строгого неравенства (<).

Пример:

s = 0
for i in range(0, n):
    for j in range(0, n):
        s += i * j

То, что его сложность равна Cn2 очевидно - внешний цикл делает n повторений. Внутренний цикл - тоже n повторений. Тело внутреннего цикла считается за константу. По правилам комбинирования вложенных циклов перемножаем сложности - получаем Cn2. Но если его сложность равна квадрату, то она и меньше либо равна квадрату. Можем написать сложность алгоритма O(n2).

В случае с o-малым нужно предъявить такую формулу, что сложность алгоритма будет строго меньше этой формулы. Например сложность этого алгоритма есть o(n3) - он работает быстрее чем любой кубический алгоритм. Или o(n2.1), o(n2+ε) для любого ε > 0, или o(n2log(n)), или ещё бесконечное число вариантов из которых нельзя выбрать один "самый подходящий".

Аналогия на числах: есть формула -x2, оцените её максимальное значение.

Простой ответ в терминах O-большого — -x2 ≤ 0. Не превосходит. А в терминах o-малого оценку привести сложнее: -x2 < 1, -x2 < 0.1, -x2 < ε (ε > 0). Если вы предъявляете конкретный ответ со строгим неравенством, сразу можно сказать что ваш ответ не самый лучший - ε можно разделить пополам и получить лучший ответ.

Лучшего ответа нет вообще. Есть последовательность ответов, каждый лучше предыдущего. Поэтому строгое неравенство непрактично использовать при оценках сверху.

2
  • о-малое -- это не просто строго меньше, это строго меньше для любого положительного множителя
    – Pak Uula
    25 фев в 13:38
  • @PakUula, константа - деталь реализации. Есть определение o-малого через "верхний предел отношения равен нулю" - совсем без констант. 25 фев в 13:48
4

Совсем на пальцах

о-малое - это не просто "меньше". Когда пишут, что сложность алгоритма - о(f), то хотят сказать, что с ростом параметра алгоритма сложность растёт гораааааааздо медленнее, чем f. Там, на бесконечности, сложность алгоритма даже в микроскоп не разглядеть по сравнению с f. Ну или как песчинка по сравнению с галактикой. Очень-очень-очень намного-намного-меньше, короче.

О-большое - это не просто "меньше или равно". Это означает, что где-то там, на бесконечности, сложность алгоритма ведёт себя примерно как f. Если совместить масштабы, то может быть даже совпадут. Ну или могут быть выбросы соответствующего размера. В случае о-малого как масштаб ни растягивай, всё равно мелко будет.

С практической точки зрения О-большое полезнее. Предположим, мы знаем, что два алгоритма имеют сложность о-малое от эн-в-кубе, o(n^3). Что это нам даёт? Ничего. А если мы знаем, что у одного сложность O(n^2), а у второго O(n*log(n))? Сразу ясно-понятно, что нужно брать второй.

но как человек, которому в жизни довелось доказывать сложность алгоритма, я думаю, что причина использования О-больших в другом

Тоже на пальцах, но чуть сложнее

Чисто из общих соображений: на ваш вопрос "Почему при оценке сложности алгоритмов используют O-большое?" ответить невозможно, так как он неверен.

При оценке сложности в специальной литературе, то есть не учебниках, используют и О-большое, и о-малое, и даже Омега-большую (Ω), омега-малую (ω) и Тета-большую (Θ). И даже используют знак ~ (тильда). Хуже того, для алгоритмов факторизации помимо О-Омега-Тета-тильда используют ещё и букву L.

Да что там специальная литература! В Википедии местами используют не только О-нотацию. Например, в статье о рекуррентных соотношениях (в английском эта теорема получила уважительное название Master theorem) текст пестрит Тета-нотацией.

И всё же, почему так широко используют О-большое? Чем О-большое удобнее о-малого? Давайте посмотрим на определение О-большого, для простоты взяв случай n ⟶ ∞:

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

Здесь U - окрестность бесконечности, то есть луч чисел n > N для некоторого N.

Что же написано в определении о-малого?

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

Видите в чём разница? В первом кванторе. Для О-большого стоит квантор существования, а для о-малого квантор всеобщности. Конечно же первый квантор доказывать гораздо проще: нашел константу C, доказал, что для всех достаточно больших n неравенство выполняется, и свободен! С квантором всеобщности дело гораздо веселее. Нужно доказывать, что |f(n)/g(n)| ⟶ 0, то есть показать что там, на бесконечности, никаких выбросов быть не может. В большинстве случаев это шибко сложно, мало кто хочет с такой фигнёй связываться.

Возьмём для примера теорему о распределении простых чисел введите сюда описание изображения

Чебышов сравнительно элементарными средствами доказал в 1850-м году, что π(x) "болтается вокруг" x/ln(x) и нашел константы, которые ограничивают отклонения. Но тот факт, что эти константы равны единице, и асимптотически π(x) сливается с x/ln(x) доказали только спустя 50 лет, причём это потребовало введения Риманом такой ниипической пушки, как дзета-функция, и аггрессивного развития теории функции комплексной переменной.

ИМХО, причина использования О-большого заключается именно в сложности доказательства теорем для о-малого.

7
  • 1
    Можете пожалуйста добавить абзац простыми словами, ну типа как для 5-классника, без всяких заумных "кванторов"? Мне кажется это сделает ответ гораздо понятнее для тех, кому эта тема не близка (и именно они задаются вопросом как топискстартер)
    – Kromster
    25 фев в 7:30
  • Кажется, сложность не доказательствах, а в отсутствии подходящих примеров. Например, алгоритм с константной сложностью. Как выразить его сложность в терминах о-малого? Мягко говоря, это очень сложно. Простой ответ - О-большое аналог нестрогого неравенства (<=), а о-малое аналог строгого (<). Ответ для нестрого неравенства формулируется значительно проще чем для строгого. 25 фев в 7:54
  • @Kromster кванторы заумны? Не понял :) Это же матанализ, первый семестр семестр первого курса. Я по простоте душевной думал, что люди, задающие вопрос "O vs o" должны были как минимум отучиться в вузе. Первый раз эти буковки возникают как раз в первом семестре, в теме про формулу Тейлора/Макларена.
    – Pak Uula
    25 фев в 7:57
  • На ютубе есть хороший канал с видео "объяснение какой-либо концепции на 5 уровнях" - ребенку, школьнику, первокурснику, аспиранту, доценту (примерно). Ну и темы разные, от бесконечности, до генной инженерии. К чему это я - почти все (и уж точно О) можно подать и в более простой форме, для затравки (как попросил автор вопроса). Впрочем право ваше, я лишь предложил улучшить ответ. Мне то вообще лень свой ответ писать ))
    – Kromster
    25 фев в 8:05
  • 1
    @PakUula, по поводу абзаца простыми словами и "... люди, задающие вопрос "O vs o" должны были как минимум отучиться в вузе ...". Это сильное допущение. Людям, вообще, не зависимо от образования, свойственно любопытство (и лень). Вот, человек, не учившийся матану (или тот, что "знал, но забыл") читает где-то про O и o и хочет быстренько понять, а где тут собака порылась, спрашивает. Может, все же, имеет смысл дать ему понимание ситуации на доступном уровне.
    – avp
    25 фев в 9:04

Ваш ответ

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

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