Почему основная теорема возвращает только тэту?

Question

Рассмотрим три случая основной теоремы для рецидивов.Тогда он всегда возвращает тэту.

Это заставляет меня задуматься, значит ли это, что он может найти только время выполнения функций, имеющих тэту?

Если да, то ограничения a> = 1 и b> 1 гарантируют, что рецидив вообще имеет тета?

Например, можно использовать повторение теоремы о слиянии Мастер, но для повторения быстрой сортировки это невозможно, поскольку быстрая сортировка не имеет тета, а только омега и большой О, который изменяется.Это так?

Answer 1

Основная теорема просто говорит вам о сложности повторения вида T(n) = a * T(n/b) + f(n).Это не имеет ничего общего с алгоритмом.Это просто математическое выражение, и вы можете точно его оценить, если знаете a, b и f.Таким образом, он также имеет точную сложность, обозначаемую Θ.

Также «функции, имеющие тета», не имеют особого смысла.Функции / алгоритмы имеют сложности, и эти сложности могут быть выражены через один или несколько входных параметров.Вы можете проанализировать множество различных сложностей для каждого алгоритма: наихудший случай, лучший случай, средний случай, сглаженная сложность и, возможно, больше.Эти сложности могут иметь верхнюю и нижнюю границы, а иногда верхняя и нижняя границы совпадают.Эти границы можно упростить, используя обозначение big-O.

Таким образом, чтобы перевести это на ваш пример быстрой сортировки:
У него наихудший случай O(n²), лучший случай Ω(n log n) и среднее значение.случай Θ(n log n) (если вы выберете правильный поворот).