假设我们构造了一个快速排序，并且枢轴值花费了线性时间。查找最坏情况下的运行时间。
我的答案：T（n）= T（n-1）+ T（1）+ theta（n）
最糟糕的情况是子阵列完全不平衡。一个子数组中有1个元素，另一子数组中有（n-1）个元素。theta（n），因为它需要运行时间n才能找到轴。
我正确地做到了吗？
您的递归基本上是正确的，但是实际上您没有进行两次递归调用。在快速排序的最坏情况下，枢轴将是数组中的最大或最小元素，因此您将在大小为n-1的一个巨型数组上递归。另一个子数组的长度为0，因此不会进行递归调用。最重要的是，每级完成的总工作量为Θ（n），因此递归关系将更合适为
T（n）= T（n-1）+Θ（n）
然后依次求解为Θ（n 2）。
希望这会有所帮助！
您无法观察到，因为根据我的研究，T（N）= T（N-K）+ T（K-1）+ n除非我们知道k的值，
T（n）= T（an /（a + b））+ T（bn /（a + b））+ n
其中a /（a + b）和b /（a + b）是所考虑数组的分数