假设我们构建了一个快速排序，并且枢轴值需要线性时间。查找最坏情况运行时间的重复。
我的答案：T(n)= T(n-1) + T(1) + theta(n)
最坏的情况发生在子阵列完全不平衡时。一个子数组中有 1 个元素，另一个子数组中有 (n-1) 个元素。theta(n) 因为它需要运行时间 n 才能找到枢轴。
我这样做正确吗？
问问题
29515 次
3 回答
2
您的递归大部分是正确的，但实际上您并没有进行两次递归调用。在快速排序的最坏情况下，枢轴将是数组中最大或最小的元素，因此您将递归一个大小为 n - 1 的巨型数组。另一个子数组的长度为 0，因此不会进行递归调用。最重要的是，完成的总工作是每个级别的 Θ(n)，因此递归关系更合适的是
T(n) = T(n - 1) + Θ(n)
然后这又解决了 Θ(n 2 )。
希望这可以帮助！
于 2013-11-05T00:53:24.393 回答
1
你无法观察，因为根据我的研究 T(N)= T(NK)+T(K-1)+n 我们无法观察到确切的值，直到我们有 k 值，
于 2016-02-12T11:53:29.493 回答
0
T(n) = T(an/(a+b)) + T(bn/(a+b)) + n
其中 a/(a+b) 和 b/(a+b) 是正在考虑的数组的分数
于 2020-02-29T17:06:43.720 回答