最烦面试官问，“为什么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))？今天给大家讲一下时间复杂度。画外音：往下看，第三种方法牛逼。第一类，简单规则，为了方便记忆，先总结几个简单的规则，预热一下。规则一：“有限操作”的时间复杂度往往是O(1)。例子：交换两个数a和b的值。voidswap(int&a,int&b){intt=a;a=b;b=t;}分析：传入一个中间变量t，进行3次操作，交换a和b的值，时间复杂度交换是O(1)。画外音：这里的运算次数有限，意思是在不增加数据量的情况下，增加运算次数。规则二：“for循环”的时间复杂度往往是O(n)。例子：找出n个数中的最大值。intmax(int[]arr,intn){inttemp=-MAX;for(inti=0;itemp)temp=arr[i];returntemp;}分析：通过一个for循环遍历数据集，每次遍历只进行“有限次数的操作”，总计算次数与输入数据量n成线性关系。规则三：“树的高度”的时间复杂度往往是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到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))呢？仍然用f(n)表示数据量为n时算法的计算次数。易知：(1)当n=1时，bs函数只计算一次画外音：无纠缠1次或1.5次，或2.7次，为常数时间。即：f(1)=1【公式A】(2)当n很大时，二进制会进行一次比较，然后向左或向右递归，使数据量减半：f(n)计算次数等于f(n/2)的计算次数，再加一次计算画外音：计算arr[mid]>target，然后将数据量减半迭代为：f(n)=f(n/2)+1【公式B】【公式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)是不是很神奇？最后是大佬，快速排序递归算法，时间复杂度的分析过程。案例三：快速排序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】画外音：（1）partition本质上是一个for，而计算次数为n；(2)二分查找只需要递归一个半区，快速排序的左半区和右半区必须递归，这个在分治减法章节有详细介绍；[公式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神剑》原创稿件，转载请联系原作者】点此阅读更多该作者好文
