最烦面试官问，“为什么XX算法的时间复杂度是OO？”以后，我再也不会害怕这样的问题了。快速排序分为几个步骤：第一步先做分区；partition以第一个元素t=arr[low]为sentinel，将数组分成两半：左半区大于t，右半区小于t。第二步左半区递归；第三步右半区递归；伪代码是：voidquick_sort(int[]arr,intlow,inthigh){if(low==high)return;inti=partition(arr,low,high);quick_sort(arr,low,i-1);quick_sort(arr,i+1,high);}为什么，快速排序，时间复杂度是O(n*lg(n))？今天我们来谈谈时间复杂度。画外音：往下看，第三种方法牛逼。***大分类，简单规则为了方便记忆，先总结几个简单的规则来热身。(1)规则一：“有限操作”的时间复杂度往往是O(1)。例子：交换两个数a和b的值。voidswap(int&a,int&b){intt=a;a=b;b=t;}分析：传入一个中间变量t，进行3次操作，交换a和b的值，时间复杂度交换是O(1)。画外音：这里的运算次数有限，意思是在不增加数据量的情况下，增加运算次数。(2)规则二：“for循环”的时间复杂度往往是O(n)。例子：找出n个数中的***值。intmax(int[]arr,intn){inttemp=-MAX;for(inti=0;itemp)temp=arr[i];returntemp;}分析：通过一个for循环遍历数据集，每次遍历只进行“有限次数的操作”，总计算次数与输入数据量n成线性关系。(3)规则三：“树的高度”的时间复杂度往往是O(lg(n))。分析：树的节点总数为n，则树的高度为lg(n)。对包含n个元素的二叉搜索树执行二分搜索的时间复杂度为O(lg(n))。弹出一个包含n个元素的堆顶元素后，调整到一个新的堆中，其时间复杂度也是O(lg(n))。第二类：组合规则通过简单规则的时间复杂度来解决组合规则的时间复杂度。例如：n号冒泡排序。voidbubble_sort(int[]arr,intn){for(inti=0;iarr[j+1])swap(arr[j],arr[j+1]);}分析：冒泡排序可以看做是三种规则的组合：外层for循环，内层for循环，最内层swap，冒泡排序的时间复杂度就是：O(n)*O(n)*O(1)=O(n^2)又如：TopK问题，通过创建一个k个元素的堆，从n个数中求解k个数中最好的问题。先用前k个元素生成一个小顶堆。这个小顶堆用来存放当前k个最近的元素。接下来从第k+1个元素开始扫描，与堆顶（堆中最小的元素）比较。如果扫描到的元素大于堆顶，则替换堆顶元素并调整堆，保证堆元素中的k个，永远是当前***的k个元素。直到扫描完n-k个元素，堆中最后的k个元素就是topK寻找的。伪代码：heap[k]=make_heap(arr[1,k]);for(i=k+1ton){adjust_heap(heep[k],arr[i]);}returnheap[k];分析：可以看到三个规则的组合：新建堆for循环调整堆，用堆求解TopK，时间复杂度为：O(k)+O(n)*O(lg(k))=O(n*lg(k))画外音：注意哪里用到加法，哪里用到乘法；其中n被使用，k被使用。第三类，递归求解简单规则和组合规则，可以用来解决非递归算法的时间复杂度。如何分析递归算法？下面通过几个案例，来说明如何通过分析递归公式来分析递归算法的时间复杂度。(1)案例一：计算1到n的和，时间复杂度分析。如果使用非递归算法：intsum(intn){intresult=0;for(inti=0;ihigh)return-1;mid=(low+high)/2;if(arr[mid]==target)returnmid;if(arr[mid]>target)returnBS(arr,low,mid-1,target);elsereturnBS(arr,mid+1,high,target);}二分查找，纯粹从递归算法分析，怎么知道它的时间复杂度是O(lg(n))呢？当数据量为n时，我们仍然用f(n)来表示算法的计算次数。很容易知道：当n=1时，bs函数只计算画外音一次：不用担心是1次，还是1.5次，还是2.7次，是常数次数.即：f(1)=1【公式A】当n很大时，二分法会进行一次比较，然后向左或向右递归，使数据量减半：f(n),等于f(n/2)的计算次数，加上画外音的1次计算：计算arr[mid]>target，然后将数据量减半，即f(n)=f(n/2)+1B]【公式B】继续展开，f(n)=f(n/2)+1f(n/2)=f(n/4)+1f(n/4)=f(n/8)+1...f(n/2^(m-1))=f(n/2^m)+1上面有m个方程，左右两边分别相加：f(n)+f(n/2)+…+f(n/2^(m-1))=[f(n/2)+1]+[f(n/4)+1]+…+[f(n/2^m)]+[1]得到：f(n)=f(n/2^m)+m再配合[公式A]：f(1)=1，即当n/2^m=1时，f(n/2^m)=1，此时m=lg(n)，这一步是分析这个算法的关键。将m=lg(n)代入其中，得到：f(n)=1+lg(n)是不是很神奇？***，大佬，快速排序递归算法，时间复杂度分析过程。(3)案例3：快速排序quick_sort，时间复杂度分析。voidquick_sort(int[]arr,intlow,inthigh){if(low==high)return;inti=partition(arr,low,high);quick_sort(arr,low,i-1);quick_sort(arr,i+1,high);}仍然用f(n)表示算法在数据量为n时的计算次数，易知：当n=1时，quick_sort函数只计算一次f(1)=1【公式A】当n很大时：第一步，先做一个分区；第二步，在左半区递归；第三步，右半区递归；即：f(n)=n+f(n/2)+f(n/2)=n+2*f(n/2)【公式B】画外音：partition本质上就是一个for，而其个数计算是n；二分查找只需要递归一个半区，而快速排序左半区和右半区都必须递归，这在分治和减法一章中有详细介绍；[公式B]不断展开，f(n)=n+2*f(n/2)f(n/2)=n/2+2*f(n/4)f(n/4)=n/4+2*f(n/8)...f(n/2^(m-1))=n/2^(m-1)+2f(n/2^m)一共有上面的m个方程，逐步带入，得：f(n)=n+2*f(n/2)=n+2*[n/2+2*f(n/4)]=2n+4*f(n/4)=2n+4*[n/4+2*f(n/8)]=3n+8f(n/8)=...=m*n+2^m*f(n/2^m)与【公式A】：f(1)=1,n/2^m=1,f(n/2^m)=1,此时m=lg(n),这一步是分析这个算法的关键。带入m=lg(n)得到：f(n)=lg(n)*n+2^(lg(n))*f(1)=n*lg(n)+n所以，快速排序的时间复杂度为n*lg(n)。Wacalei，这很有趣！画外音：嗯，估计有83%的同学没有仔细研究。如果你花5分钟思考以上过程，你一定会有所收获。综上所述，for循环的时间复杂度往往是O(n)树的高度的时间复杂度往往是O(lg(n))二分查找的时间复杂度是O(lg(n)),快速排序n*(lg(n))递归解的时间复杂度，以后再问时间复杂度，你就知道是什么，为什么了。想法比结论更重要。【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此阅读更多该作者好文
