快排 时间复杂度递归公式,递归算法时间复杂度计算

废话

上课没有好好听，一直没有弄懂这个递归的时间复杂度怎么算，时间复杂度全靠背，然后一次面试，人家问我这个具体怎么算的，当时就很尴尬，所以我一定要弄懂它，特此记录。
先上个图：

为什么要学会算时间复杂度

我以前只认为时间复杂度不重要，这个不会也就不会了，直到面试被问到，发现自己确实该好好学习了，从小说是这是基础，从大说你在做编程题的时候，不懂时间复杂度，很多限制你不懂，也过不了,再者这个面试当中问的挺多的。

稳定的含义

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
以下的算法都是按照O(1) = O(0)即忽略常数项

冒泡排序 public void Sort(int[] nums) { for(int i = 1;i < nums.length;i++){ for (int j = 0; j < nums.length; j++) { if(nums[i] < nums[j]){ nums[i] = nums[j] ^ nums[i]; nums[j] = nums[j] ^ nums[i]; nums[i] = nums[j] ^ nums[i]; } } } }

核心必定是两个for的运算了,N = nums.length,那么可以直接看出时间复杂度为O(N^2),从着看就很简单对吧，但是加入递归如何？这就需要递推式，当时看确实看不懂现在看就很清楚了

快排 /*** 快速排序*/public class QuickSort { public void Sort(int[] nums) { QuickSort(nums,0,nums.length - 1); } private void QuickSort(int[] nums,int left,int right){ if(left >= right ){ return; } int pivot = getMedian(nums,left,right); int i = left; int j = right - 1; for(;;){ while (nums[++i] < pivot){} while (nums[--j] > pivot){} if(i < j){ swap(nums,i,j); }else { break; } } //将中枢元换回来 swap(nums,i,right - 1); QuickSort(nums,left,i - 1); QuickSort(nums,i + 1,right); } //三中值分割法 public int getMedian(int[] nums,int left,int right){ int center = (left + right) / 2; if(nums[center] < nums[left]){ swap(nums,left,center); } if(nums[left] > nums[right]){ swap(nums,left,right); } if(nums[right] < nums[center]){ swap(nums,right,center); } //提供一个警戒位置，防止i跑过端点 //left可以给j提供一个警戒位置，防止j跑过端点 swap(nums,center,right - 1); return nums[right - 1]; } public void swap(int[] nums,int x,int y){ int tmp; tmp = nums[x]; nums[x] = nums[y]; nums[y] = tmp; }}

首先要明白快排中什么是主要部分。
1.找到中枢元，分割
2.前半部分的递归
3.后半部分的递归
设前半部分的的数量是i个那么就会得到如下的递归式

前半部分的递归时间
T（i），这个T（）在我看来就是i个元素进入递归然后返回的时间后半部分的递归
T（N - i - 1) 这个相当于是另外一半递归的时间，至于-1是因为减去中枢元找到中枢元是常数时间所以不计算，c（N）是分割时间
c（N）相当于是分割的时间
所以递归的递推式为
T(N) = T(i） + T（N - i - 1） + c（N） 最好情况

i = N / 2 代表中枢元选的好，刚好是这个分割后元组的一半故：
T(N) = T(N/2)+T(N/2 ) + c（N）化简以下得（-1这里不需要了，因为两边是一样的）
然后同时除以N
T(N)/N = T(N/2)/（N/2)+ c
将N替换为N/2,一直替换到2(这里用了一种方法，其实和递归树法差不多一样，只不过一个是在原式子上扩展，另一个是扩展为多个式子再消去）
T(N/2)/N/2 = T(N/4)/（N/4)+ c
T(N/4)/（N/4) = T(N/8)/（N/8)+c
…
T(2) = T(1) + c
然后将这些式子加在一起化简，化简为，c的个数符合logn的规律（数学问题不详细解释了）
T(N)/N = T(1) + clogN
然后给两边乘以N得
T(N) = N + cNlogN
根据大O表示法自然是去掉小的时间，保留最大的所以O（NlogN）为快排时间复杂度

最坏的情况

i = 0 的时候，由于中枢元选的不好，导致一侧是满的。
例如：243 235 43 2553 46 1
我选1为中枢元，那么全部的数都要放到1后面
得到递推关系式：（这里不能把-1去掉，不然就直接无意义了）
T(N) = T(N - 1) + cN
和上面手段一样
T(N - 1) = T(N - 2) + c（N - 1)
…
T(2)=T(1)+c（2）
加在一起化简得：（很明显cN的个数是个等差数列，那必定有N^2）
T(N) = T(1) + cN^2
所以T（N） = N^2

归并排序

归并排序每次都是分成N/2所以类似于快排中的，最好的情况，由于两次递归加上合并用时为N，合并就是需要将一个数组复制到另一个所以为N。一共复制N个数，由于没有了可变的数i，所以它最好最差都是一样的。
得到递推关系式：
T(N)=2T(N/2)+N
同时除以N
T(N)/N =T(N/2)/(N/2) + 1
还是类似一直带入
T(N/2)/(N/2) = T(N/4)/(N/4) + 1
…
T(2)/2 =T(1)/1 + 1
加一起得
T(N)/(N) = T(1) + 1
T(N) = N + NlogN = O(NlogN）

什么样的排序是最好的？

混合排序，例如java当中Arrays.sort()函数中，如果数组小于10个元素使用的是插入排序，大于10就使用快速排序。此时的时间复杂度递推式应该是
T(N) = O(N^2) N <= 10
T(N) = T(i）+T(N - i - 1） + cN N >10
分别求解就行