Question

快速排序最差时间复杂度递归公式 t(n-1)

求时间复杂度
已知一算法的时间复杂度上界函数满足递归关系T（n）=n + T（n-1），那么该算法的渐进时间复杂度为？

Answer 1

T(n) = n+T(n-1) =n+n-1+T(n-2)=...=n+(n-1)+(n-2)+...+1+T(0)=(1+n)*n/2=O(n^2)

理论计算机研究中，衡量算法一般从两个方面分析：时间复杂度和空间复杂度。空间复杂度跟时间复杂度是类似的，下面简单解释一下时间复杂度：对于一个数据规模为n的问题，解决该问题的算法所用时间可以用含有n的函数T(n)来表示。

对于绝大多数情况，只需要了解算法的一般性能而不考虑细节，也就是说，我们只关心函数T(n)的表达式的形式，而不关心表达式的常数系数等与数据规模没有关系的量值。

对于函数T(n)，我们又进一步将它简化为O(n)，即只考虑算法平均运行时间的“瓶颈”，也就是T(n)表达式中，关于变量n增长最快的哪一项。

扩展资料：

二进制整数的基数排序是一个非常特殊的情形，因为只有两个数字 0 和 1，故每次将数据分成 2 个小组。假设所有数据属于[0，21+m-1], m 为一整数，则先根据最高位（m 位）的数字将数据分成 2 个小组，分别属于[0，2m-1]和[2m，21 + m-1]；

根据次高位（m-1 位）的数字将[0，2m-1]的数据分成 2 个小组，分别属于[0，21 - m-1]和[21 - m，2m-1]，将[2m，21 + m-1]的数据分成 2 个小组，分别属于[2m，2m+21 - m-1]和[2m+21 - m，21 + m-1]；……；这完全类似于快速排序的分治算法结构，因而可以类似于快速排序实现该算法。

参考资料来源：百度百科-超快速排序

Answer 2

T(n) = n+T(n-1) =n+n-1+T(n-2)=...=n+(n-1)+(n-2)+...+1+T(0)=(1+n)*n/2=O(n^2)