最坏情况快速排序的主定理
Master theorem for worst case quicksort
我知道如何计算主定理，并且我设法针对最佳和平均情况计算了它。
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 在评论中指出的那样，主定理不适用于您在此处提出的递归。
给出一些关于为什么会这样的背景 - 主定理是专门为
的情况设计的
- 子问题的个数是常数，并且
- 子问题的大小呈几何衰减。
在这种情况下，第二个要求不成立，因为您的递归问题规模呈线性衰减而不是几何衰减。
你是对的，但是，递归求解为 Θ(n2)。要了解原因，请注意，如果您展开重复，您会得到成本为
Θ(n + (n-1) + (n-2) + ... + 2 + 1)
= Θ(n(n+1)/2)
= Θ(n2).
希望对您有所帮助！
我知道如何计算主定理，并且我设法针对最佳和平均情况计算了它。
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 在评论中指出的那样，主定理不适用于您在此处提出的递归。
给出一些关于为什么会这样的背景 - 主定理是专门为
的情况设计的- 子问题的个数是常数，并且
- 子问题的大小呈几何衰减。
在这种情况下，第二个要求不成立，因为您的递归问题规模呈线性衰减而不是几何衰减。
你是对的，但是，递归求解为 Θ(n2)。要了解原因，请注意，如果您展开重复，您会得到成本为
Θ(n + (n-1) + (n-2) + ... + 2 + 1)
= Θ(n(n+1)/2)
= Θ(n2).
希望对您有所帮助！