Просьба, если в ответе решите использовать высшую математику, переведите сразу на обыденный язык, чтобы все было понятно и не возникло новых вопросов.
2 ответа
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). Если вы предъявляете конкретный ответ со строгим неравенством, сразу можно сказать что ваш ответ не самый лучший - ε можно разделить пополам и получить лучший ответ.
Лучшего ответа нет вообще. Есть последовательность ответов, каждый лучше предыдущего. Поэтому строгое неравенство непрактично использовать при оценках сверху.
-
о-малое -- это не просто строго меньше, это строго меньше для любого положительного множителя– Pak Uula25 фев в 13:38
-
@PakUula, константа - деталь реализации. Есть определение o-малого через "верхний предел отношения равен нулю" - совсем без констант. 25 фев в 13:48
Совсем на пальцах
о-малое - это не просто "меньше". Когда пишут, что сложность алгоритма - о(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 лет, причём это потребовало введения Риманом такой ниипической пушки, как дзета-функция, и аггрессивного развития теории функции комплексной переменной.
ИМХО, причина использования О-большого заключается именно в сложности доказательства теорем для о-малого.
-
1Можете пожалуйста добавить абзац простыми словами, ну типа как для 5-классника, без всяких заумных "кванторов"? Мне кажется это сделает ответ гораздо понятнее для тех, кому эта тема не близка (и именно они задаются вопросом как топискстартер)– Kromster25 фев в 7:30
-
Кажется, сложность не доказательствах, а в отсутствии подходящих примеров. Например, алгоритм с константной сложностью. Как выразить его сложность в терминах о-малого? Мягко говоря, это очень сложно. Простой ответ - О-большое аналог нестрогого неравенства (<=), а о-малое аналог строгого (<). Ответ для нестрого неравенства формулируется значительно проще чем для строгого. 25 фев в 7:54
-
@Kromster кванторы заумны? Не понял :) Это же матанализ, первый семестр семестр первого курса. Я по простоте душевной думал, что люди, задающие вопрос "O vs o" должны были как минимум отучиться в вузе. Первый раз эти буковки возникают как раз в первом семестре, в теме про формулу Тейлора/Макларена.– Pak Uula25 фев в 7:57
-
На ютубе есть хороший канал с видео "объяснение какой-либо концепции на 5 уровнях" - ребенку, школьнику, первокурснику, аспиранту, доценту (примерно). Ну и темы разные, от бесконечности, до генной инженерии. К чему это я - почти все (и уж точно О) можно подать и в более простой форме, для затравки (как попросил автор вопроса). Впрочем право ваше, я лишь предложил улучшить ответ. Мне то вообще лень свой ответ писать ))– Kromster25 фев в 8:05
-
1@PakUula, по поводу абзаца простыми словами и
"... люди, задающие вопрос "O vs o" должны были как минимум отучиться в вузе ..."
. Это сильное допущение. Людям, вообще, не зависимо от образования, свойственно любопытство (и лень). Вот, человек, не учившийся матану (или тот, что "знал, но забыл") читает где-то про O и o и хочет быстренько понять, а где тут собака порылась, спрашивает. Может, все же, имеет смысл дать ему понимание ситуации на доступном уровне.– avp25 фев в 9:04
o
-малое выглядит более строгим требованием, чемO
-большое, что влечёт трудности с практическим применением. Когда говорят, имеет сложностьO(N^2)
, то подразумевается, что сложность действительно может быть квадратичной. Когда говорят имеет сложностьo(N^2)
, то имеется ввиду, что сложность будет гарантированно лучше, чем квадратичная. Например для линейного поиска в массиве можно сказать, что он имеет сложностьO(N)
, но нельзя сказатьo(N)
. Можно сказать, что он имеет сложностьo(N * log(N))
, но это сбивает с толку.O
-большое сразу наглядно демонстрирует худший случай, аo
-малое показывает некоторую недостижимую границу, и не совсем очевидно, что на самом деле представляет из себя худший случай.o
-малое тоже используется при оценки алгоритмов. Хороший пример — это коллекцииMap
иSet
в javascript. Спецификация языка требует, чтобы время доступа к элементу коллекции в среднем было сублинейным (24.1 Map Objects), т.е. в среднем имело сложностьo(n)
. В терминахO
-большого это может быть сложность,например,O(1)
, илиO(log(n))
, или дажеO(sqrt(n))
.