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

Question

С ссылкой на этот ответ , что такое Тета (жесткая граница)?

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

Answer 1

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

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

Answer 2

& тета-нотация (тэта-нотация) называется тесно связанной, потому что она более точна, чем O-нотация и & Omega;-нотация (омега-запись ).

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

Обозначение

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

Answer 3

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

Если у вас есть что-то, что & Omega; (f (n)) , это означает, что есть k , g (n) , такие что f (n) & ge; кг (n) .

А если у вас есть что-то с O (f (n)) и & Omega; (f (n)) , то это & Theta; (е (п) * * * тысяча тридцать две тысяча тридцать три *. Статья Википедии приличная, хотя и немного плотная.

Answer 4

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

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

Как правило, O-notation используется для сложности верхней границы.

---

Асимптотически жесткая граница (c ₁ g (n) & f (n) & # x2264; c ₂ g (n)) показывает среднюю сложность границ для функции, имеющей значение между пределами границ (верхняя граница и нижняя граница), где c ₁ и c ₂ являются константами.

Answer 5

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

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

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

Answer 6

Точно нижняя граница или $ \ 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 $ дает нам самый низкий предел.

Answer 7

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

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

Answer 8

Основная разница между

Blockquote

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

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