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

Θ-нотации (тета-нотация) называется tight-bound, потому что это более точно, чем о-нотация и Ω-обозначения (нотации омега).

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

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

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

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

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

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

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

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

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

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

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

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

Blockquote

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

Асым. tightbound bound показывает для eg(c1g(n)