Каково различие между нижней границей и трудный связанный?

В отношении этого ответа, что такое Тета (трудный связанный)?

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

94
задан nbro 27 July 2019 в 23:33
поделиться

4 ответа

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

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

148
ответ дан nbro 24 November 2019 в 05:59
поделиться

Θ - нотацию (нотация теты) называют трудно-ограниченной, потому что это более точно, чем O-нотация и Ω - нотация (нотация омеги).

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

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

107
ответ дан Bill the Lizard 24 November 2019 в 05:59
поделиться

Если у Вас есть что-то, что это O (f (n)) , который означает, что существует, k, г (n) таким образом что f (n) К g (n) .

, Если у Вас есть что-то, которое это Ω (f (n)) , который означает, существует, k, г (n) таким образом что f (n) К g (n) .

И если у Вас есть что-то с [1 111] O (f (n)) и Ω (f (n)) , тогда это Θ (f (n) .

статья Wikipedia достойна, если немного плотный.

16
ответ дан Charlie Martin 24 November 2019 в 05:59
поделиться

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

Используя массив ищут в принятом ответе на другой вопрос как пример. Время, которое требуется для нахождения конкретного числа в списке размера n, является n/2 * some_constant в среднем. При обработке его как функции f(n) = n/2*some_constant это увеличивается не быстрее, чем g(n) = n в смысле, как дал Charlie. Кроме того, это увеличивается не медленнее, чем g(n) также. Следовательно, g(n) на самом деле и верхняя граница и нижняя граница f(n) в Нотации "большого О", таким образом, сложность линейного поиска точно n, означая, что это - Тета (n).

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

3
ответ дан PolyThinker 24 November 2019 в 05:59
поделиться
Другие вопросы по тегам:

Похожие вопросы: