假设我们构造了一个快速排序，并且枢轴值需要线性时间。求最坏情况下运行时间的递归式
我的回答:T(n)= T(n-1) + T(1) + (n)
最坏的情况是子数组完全不平衡。一个子数组中有1个元素，另一个子数组中有(n-1)个元素。(n)因为它需要运行时间n来找到主节点
我这样做对吗?
您的递归大部分是正确的，但实际上您并没有进行两次递归调用。在快速排序的最坏情况下，主节点是数组中最大或最小的元素，所以你会在一个大小为n - 1的大数组上循环。另一个子数组的长度为0，因此不进行递归调用。最重要的是，每层完成的总功是Θ(n)，因此递归关系更合适为
T(n) = T(n - 1) + Θ(n)
这又解为Θ(n2)。
希望这对你有帮助!
你不能观察，因为根据我的研究，T(N)= T(N- k)+T(K-1)+ N我们不能观察到确切的值，直到我们k的值
T (n) =(一个/(a + b)) + T (bn/(a + b)) + n
其中a/(a+b)和b/(a+b)是所考虑的数组的部分