Я знаю, как вычислить основную теорему, и мне удалось вычислить ее для лучшего и среднего случая. T(n) = 2T(n/2) + Theta(n)
Уравнение наихудшего случая - T(n) = T(n-1) + Theta(n). Если я прав, a равно 1, b равно n / (n-1) и f (n) равно n. Но как мне выбрать правильный случай основной теоремы и получить наихудшую временную сложность Theta (n ^ 2)?
Спасибо!
Как отметил @DavidEisenstat в комментариях, основная теорема не применяется к повторению, которое вы здесь придумали.
Чтобы дать некоторый контекст относительно того, почему это так - основная теорема специально разработана для случая, когда
В этом случае второе требование не выполняется, так как при повторении размер проблемы уменьшается линейно, а не геометрически.
Вы правы, однако, что повторение решает Θ (n 2). Чтобы понять, почему, обратите внимание, что если вы развернете повторение, вы получите, что стоимость
Θ(n + (n-1) + (n-2) + ... + 2 + 1)
= Θ(n(n+1)/2)
= Θ (n 2).
Надеюсь это поможет!
