Каково различие между нижней границей и трудный связанный?
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).
Θ - нотацию (нотация теты) называют трудно-ограниченной, потому что это более точно, чем O-нотация и Ω - нотация (нотация омеги).
, Если я был ленив, я мог бы сказать, что двоичный поиск на сортированном массиве является O (n <глоток> 2 ), O (n <глоток> 3 ) и O (2 <глоток> n ), и я был бы технически корректен в каждом случае. Поэтому O-нотация только определяет верхняя граница , и двоичный поиск ограничен на высокой стороне всеми теми функциями, просто не очень тесно. Эти ленивые оценки были бы бесполезны .
Θ - нотация решает эту проблему объединение O-нотация и Ω - нотация. Если я говорю, что двоичный поиск является Θ (зарегистрируйте n), который дает Вам более точную информацию. Это говорит Вам, что алгоритм ограничен на оба стороны заданной функцией, таким образом, это никогда не будет значительно быстрее или медленнее, чем установленный.
Если у Вас есть что-то, что это 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) .
Фразы минимальное время и максимальное время являются немного вводящими в заблуждение здесь. Когда мы говорим о больших нотациях 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) является верхней границей, потому что алгоритм может работать в постоянное время за некоторыми исходными данными (это лучший случай , я упомянул выше, который не является действительно, что мы хотим знать во время выполнения).