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

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

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

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).

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

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

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

Если у вас есть что-то 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) .

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

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

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

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

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

Фразы минимальное и максимальное время здесь немного вводят в заблуждение. Когда мы говорим о нотации больших 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) является верхней границей, потому что алгоритм может работать в постоянное время для некоторых входных данных (это лучший случай, о котором я упоминал выше, что на самом деле не то, что мы хотим знать о времени работы).

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

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

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

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

Цитата

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

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