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

Question

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

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

Если у вас есть что-то & # 937; (f (n)) , это означает, что есть k , g (n) такой, что f (n) & # 8805; k g (n) .

А если у вас есть что-то с O (f (n)) и & # 937; (f (n)) , тогда это & # 920; (f (n) .

статья в Википедии приличная, хотя и немного плотная.

Answer 4

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

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

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

<Ч>

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

Answer 5

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

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

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

Answer 6

  

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

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

Answer 7

Точно нижняя граница или $ omega $ bfon f (n) означает набор функций, которые асимптотически менее или равны f (n), т. Е. u u g (n) ≤ cf (n) $ для всех $ `un≥ n n 'Для некоторых C, n' $ in $ bbb {n} $

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

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

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

$\theta $

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

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

Answer 8

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

Цитата

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

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