В чем разница между нижней границей и жесткой границей?

100

Со ссылкой на этот ответ , что такое Тета (жесткая связь)?

Omega - это нижняя граница, вполне понятная, минимальное время, которое может занять алгоритм. И мы знаем, что Big-O предназначен для верхней границы, что означает максимальное время, которое может занять алгоритм. Но я понятия не имею о Theta.

Адил Ансари
источник

Ответы:

155

Big O - это верхняя граница, а Omega - нижняя граница. Для теты требуются как Big O, так и Omega, поэтому она называется жесткой границей (это должна быть как верхняя, так и нижняя граница).

Например, алгоритм Omega(n log n)занимает как минимум n log nвремя, но не имеет верхнего предела. Выбор алгоритма Theta(n log n)намного предпочтительнее, поскольку он занимает не менее n log n (Omega n log n) и не более n log n (Big O n log n).

Крис Банч
источник
7
Ох .. Теперь термин "жесткая привязка" кажется мне самоочевидным. Спасибо, Крис. Глупый я, возможно, я ожидал какой-то сложной идеи. :)
Adeel Ansari
6
Да, есть много причудливых обозначений, но они не слишком сложны, если вы их запомните.
Крис Банч
4
Этот свободно доступный документ от Virginia Tech объясняет на примерах различия в производительности между алгоритмами разной сложности и кратко объясняет асимптотический анализ: people.cs.vt.edu/shaffer/Book/C++3e20120102.pdf
Алан,
Что вы имеете в виду под словами «Алгоритм, принимающий Theta (n log n), гораздо предпочтительнее, так как он требует не менее n log n (Omega n log n) и не более n log n (Big O n log n)» в, это точная сложность алгоритма, как вы написали, по крайней мере, Omega (nlogn) и при макс BigO (nlogn)?
Nikhil Verma
1
Проще говоря, можем ли мы назвать: верхнюю границу (Big (O)) худшим случаем? жесткий переплет как средний случай? нижняя граница (омега) в лучшем случае?
Revanth,
113

Θ-нотация (тета-нотация) называется жестко связанной, потому что она более точна, чем O-нотация и Ω-нотация (нотация омега).

Если бы я был ленив, я мог бы сказать, что двоичный поиск в отсортированном массиве - это O (n 2 ), O (n 3 ) и O (2 n ), и я был бы технически прав во всех случаях. Это потому, что O-нотация определяет только верхнюю границу , а двоичный поиск ограничен сверху всеми этими функциями, но не очень близко. Эти ленивые оценки бесполезны .

-Нотация решает эту проблему путем комбинирования O-нотации и Ω-нотации. Если я скажу, что двоичный поиск - это (log n), это даст вам более точную информацию. Он сообщает вам, что алгоритм ограничен с обеих сторон данной функцией, поэтому он никогда не будет значительно быстрее или медленнее, чем указано.

Билл Ящерица
источник
11
If I were lazy, I could say that binary search on a sorted array is O(n2), O(n3), and O(2n), and I would be technically correct in every case- Кажется, что большинство людей в компьютерном мире ленивы только потому, что все в основном говорят только о сложностях Big O.
RBT
If I were lazy, I could say that binary search on a sorted array is O(n2), O(n3), and O(2n), and I would be technically correct in every caseВ случае, если кого-то это смущает: для такого рода функций, которые не являются асимптотически жесткими, используется нотация маленького о. Пример: - Граница 2n ^ 2 = O (n ^ 2) асимптотически точна, а оценка 2n = O (n ^ 2) - нет. Подробнее: stackoverflow.com/questions/1364444/…
Драгос Стругар
18

Если у вас есть что-то O (f (n)), это означает, что есть k , g (n), такие что f (n)kg (n) .

Если у вас есть что-то, что есть Ω (f (n)), это означает, что существуют k , g (n) такие, что f (n)kg (n) .

И если у вас есть что-то с O (f (n)) и Ω (f (n)) , то это Θ (f (n) .

Статья Википедии является достойной, если немного густой.

Чарли Мартин
источник
Теперь читаю семейство обозначений Бахмана-Ландау. Спасибо, Чарли, я ходил туда раньше, но вернулся, не вдаваясь в подробности.
Adeel Ansari
Эй, хорошо бы время от времени узнавать о докторских программах.
Чарли Мартин
Обратите внимание, что нотация Ландау с большим О не ограничивается алгоритмической сложностью.
Чарли Мартин,
Это выглядит неправильно. В первой строке должно быть написано «Если у вас есть что-то, что O (g (n))», то есть gвместо f, а остальное можно оставить как есть. То же самое и со второй строкой: она должна быть «Если у вас есть что-то, что есть Ω (g (n))». Не могли бы вы проверить еще раз?
Фабио говорит: "Восстановите Монику"
Вся тема настолько запутана, что кто-то с таким авторитетом тоже может ошибиться: D Шутя в сторону, кому-то нужно исправить этот ответ. Это сбивает людей с толку (меня это очень сильно беспокоило).
Rad
5

Асимптотическая верхняя граница означает, что данный алгоритм выполняется в течение максимального времени, в зависимости от количества входов.

Возьмем для примера алгоритм сортировки. Если все элементы массива расположены в порядке убывания, то для их сортировки потребуется время выполнения O(n), показывающее сложность верхней границы. Если массив уже отсортирован, значение будет O(1).

Обычно O-notationиспользуется для оценки сложности сверху.


Асимптотически точная граница (c 1 g (n) ≤ f (n) ≤ c 2 g (n)) показывает среднюю граничную сложность для функции, имеющей значение между граничными пределами (верхняя граница и нижняя граница), где c 1 и c 2 - константы.

Sameenu
источник
1
если массив отсортирован, граница по-прежнему будет O (n)
Арун Аравинд
2
@ArunAravind Вы можете объяснить, почему?
nbro
3

Фразы минимальное и максимальное время здесь немного вводят в заблуждение. Когда мы говорим о нотации больших O, нас интересует не реальное время, а то, как время увеличивается, когда размер нашего ввода становится больше. И обычно мы говорим о среднем или наихудшем случае, а не о лучшем случае , который обычно не имеет значения для решения наших проблем.

Использование поиска по массиву в принятом ответе на другой вопрос в качестве примера. Время, необходимое для нахождения определенного числа в списке размера n, в среднем равно n / 2 * some_constant. Если рассматривать его как функцию f(n) = n/2*some_constant, он увеличивается не быстрее, чем g(n) = nв том смысле, который дал Чарли. Кроме того, он увеличивается не медленнее, чем g(n)оба. Следовательно, g(n)на самом деле это верхняя и нижняя границы f(n)в нотации Big-O, поэтому сложность линейного поиска равна точно n , что означает, что это Theta (n).

В этом отношении объяснение в принятом ответе на другой вопрос не совсем правильное, в котором утверждается, что O (n) является верхней границей, потому что алгоритм может работать в постоянное время для некоторых входных данных (это лучший случай, о котором я упоминал выше, что на самом деле не то, что мы хотим знать о времени работы).

PolyThinker
источник
Итак, можем ли мы сказать, что Ω - лучший случай, а O - худший? . .. и следует ли заменить термины «лучший случай» и «худший случай» соответственно?
Adeel Ansari
В лучшем случае O (1) для любой проблемы?
Зак Лэнгли
1
@Adeel, нет, Theta и O могут относиться как к среднему, так и к худшему случаю. @ Зак, ну не совсем так. Спасибо что подметил это.
PolyThinker
0

Если бы я был ленив, я мог бы сказать, что двоичный поиск в отсортированном массиве - это O (n2), O (n3) и O (2n), и я был бы технически прав во всех случаях.

Мы можем использовать о-нотацию ("little-oh") для обозначения верхней границы, которая не является асимптотически точной. И big-oh и little-oh похожи. Но big-oh, вероятно, используется для определения асимптотически точной верхней границы.

Финн отсутствует
источник
0

А именно, нижняя граница или $ \ omega $ bfon f (n) означает набор функций, которые асимптотически меньше или равны f (n), т.е. U g (n) ≤ cf (n) $ \ для всех $ `un≥ n 'Для некоторых c, n' $ \ in $ $ \ Bbb {N} $

А верхняя граница или $ \ mathit {O} $ на f (n) означает набор функций, которые асимптотически больше или равны f (n), что математически говорит,

$ g (n) \ ge cf (n) \ для всех n \ ge n '$, для некоторых c, n' $ \ in $ \ Bbb {N} $.

Теперь $ \ Theta $ является пересечением двух указанных выше

$\theta $

Например, если алгоритм похож на «точно $ \ Omega \ left (f (n) \ right $», то лучше сказать, что это $ \ Theta \ left (f (n) \ right) $.

Или мы можем также сказать, что он дает нам фактическую скорость, которая $ \omega $дает нам самый низкий предел.

П.И. Гоголь
источник
-2

Основное различие между

Цитата

асимптотически верхняя граница и асимптотически плотная Asym.upperbound означает данный алгоритм, который может выполняться с максимальным количеством времени в зависимости от количества входов, например, в алгоритме сортировки, если все элементы массива (n) находятся в порядке убывания, то для их возрастания он займет время O (n), что показывает сложность верхней границы, но если они уже отсортированы, тогда потребуется ohm (1). Поэтому мы обычно использовали обозначение «O» для сложности верхней границы.

Асим. жесткая граница показывает, что for eg (c1g (n) <= f (n) <= c2g (n)) показывает предел жесткой границы, так что функция имеет значение между двумя границами (верхняя граница и нижняя граница), что дает средний случай.

БОББИ Z
источник
2
Вы не должны отвечать на старые вопросы, если ваш ответ ничего не добавляет к уже принятым ответам.
alestanis