快排是我们比较熟悉的一种排序方式，以前我们知道，快排时间复杂度最佳时0(nlogn),最差是O(n2)，那么究竟是为什么呢？
这里我们并不做多严格的数学验证，我们知道，对于划分成子问题求解的问题，我们可以用下面的公式
T(n) = a*T(n/b)+f(n) 来求得其时间复杂度，如果a=b=2时，即每次划分都是按照折半划分，那么其时间复杂度是0(nlogn),但是我们考虑另外一种极端的情况，就是每次划分都是
T(n) = T(n-1)+T(1)+f(n),这就是我们平时说的有序的情况，如1,2,3,4,5,那么每次第一次划分的地方就是1，这样其实就退化成0（n2）.
阅读(19804) | 评论(0) | 转发(0) |
