快速排序和二分查找时间复杂度详解
一次二分剩下：n/2
兩次二分剩下：n/2/2 = n/4
。。。
m次二分剩下：n/(2^m)
在最壞情況下是在排除到只剩下最后一個值之后得到結果，所以為
n/(2^m)=1;
2^m=n;
所以時間復雜度為：log2(n)
快速排序的基本思想是：每次從無序的序列中找出一個數作為中間點（可以把第一個數作為中間點），然后把小于中間點的數放在中間點的左邊，把大于中間點的數放在中間點的右邊；對以上過程重復log(n)次得到有序的序列。
? ? 快速排序的時間復雜性分析：排序的大體如下圖所示，假設有1到8代表要排序的數，快速排序會遞歸log（8）=3次，每次對n個數進行一次處理，所以他的時間復雜度為n*log(n)。所以排序問題的時間復雜度可以認為是對排序數據的總的操作次數。
哈哈，話說真心有點兒不理解，國外的親們真是有意思，這舞蹈一跳，丫的瞬間就明白了所謂的快速排序。建議國內教授計算機算法的老師都看一下這個系列的舞蹈，很給力。 話說已經有了充分的分析，以下文章轉自：http://chenzehe.iteye.com/blog/481188
快速排序的時間主要耗費在劃分操作上，對長度為?k?的區間進行劃分，共需?k-1?次關鍵字的比較。
?
最壞時間復雜度：最壞情況是每次劃分選取的基準都是當前無序區中關鍵字最小（或最大）的記錄，劃分的結果是基準左邊的子區間為空（或右邊的子區間為空），而劃分所得的另一個非空的子區間中記錄數目，僅僅比劃分前的無序區中記錄個數減少一個。因此，快速排序必須做?n-1?次劃分，第?i?次劃分開始時區間長度為?n-i-1,?所需的比較次數為?n-i(1<=i<=n-1),?故總的比較次數達到最大值?Cmax =n(n-1)/2=O(n^2)?。如果按上面給出的劃分算法，每次取當前無序區的第?1?個記錄為基準，那么當文件的記錄已按遞增序（或遞減序）排列時，每次劃分所取的基準就是當前無序區中關鍵字最小（或最大）的記錄，則快速排序所需的比較次數反而最多。
?
最好時間復雜度：在最好情況下，每次劃分所取的基準都是當前無序區的“中值”記錄，劃分的結果與基準的左、右兩個無序子區間的長度大致相等。總的關鍵字比較次數為?O(n×lgn)。
?
用遞歸樹來分析最好情況下的比較次數更簡單。因為每次劃分后左、右子區間長度大致相等，故遞歸樹的高度為?O(lgn),而遞歸樹每一層上各結點所對應的劃分過程中所需要的關鍵字比較次數總和不超過?n，故整個排序過程所需要的關鍵字比較總次數?C(n)=O(n×lgn)?。因為快速排序的記錄移動次數不大于比較的次數，所以快速排序的最壞時間復雜度應為?O(n^2 )，最好時間復雜度為?O(n×lgn)。
?
基準關鍵字的選取：在當前無序區中選取劃分的基準關鍵字是決定算法性能的關鍵。 ① “三者取中”的規則，即在當前區間里，將該區間首、尾和中間位置上的關鍵字比較，以三者之中值所對應的記錄作為基準，在劃分開始前將該基準記錄和該區的第?1?個記錄進行交換，此后的劃分過程與上面所給的?Partition?算法完全相同。 ② 取位于?low?和?high?之間的隨機數?k(low<=k<=high),?用?R[k]?作為基準；選取基準最好的方法是用一個隨機函數產生一個位于?low?和?high?之間的隨機數?k(low<=k<=high),?用?R[k]?作為基準?,?這相當于強迫?R[low..high]?中的記錄是隨機分布的。用此方法所得到的快速排序一般稱為隨機的快速排序。隨機的快速排序與一般的快速排序算法差別很小。但隨機化后，算法的性能大大提高了，尤其是對初始有序的文件，一般不可能導致最壞情況的發生。算法的隨機化不僅僅適用于快速排序，也適用于其他需要數據隨機分布的算法。
?
平均時間復雜度：盡管快速排序的最壞時間為?O(n^2 ),?但就平均性能而言，它是基于關鍵字比較的內部排序算法中速度最快的，快速排序亦因此而得名。它的平均時間復雜度為?O(n×lgn)。
?
空間復雜度：快速排序在系統內部需要一個棧來實現遞歸。若每次劃分較為均勻，則其遞歸樹的高度為?O(lgn),?故遞歸后所需棧空間為?O(lgn)?。最壞情況下，遞歸樹的高度為?O(n),?所需的棧空間為?O(n)?。
?
穩定性：快速排序是非穩定的。
哈哈，話說真心有點兒不理解，國外的親們真是有意思，這舞蹈一跳，丫的瞬間就明白了所謂的快速排序。建議國內教授計算機算法的老師都看一下這個系列的舞蹈，很給力。話說已經有了充分的分析，以下文章轉自： http://chenzehe.iteye.com/blog/481188
快速排序的時間主要耗費在劃分操作上，對長度為?k?的區間進行劃分，共需?k-1?次關鍵字的比較。
?
最壞時間復雜度：最壞情況是每次劃分選取的基準都是當前無序區中關鍵字最小（或最大）的記錄，劃分的結果是基準左邊的子區間為空（或右邊的子區間為空），而劃分所得的另一個非空的子區間中記錄數目，僅僅比劃分前的無序區中記錄個數減少一個。因此，快速排序必須做?n-1?次劃分，第?i?次劃分開始時區間長度為?n-i-1,?所需的比較次數為?n-i(1<=i<=n-1),?故總的比較次數達到最大值?Cmax =n(n-1)/2=O(n^2)?。如果按上面給出的劃分算法，每次取當前無序區的第?1?個記錄為基準，那么當文件的記錄已按遞增序（或遞減序）排列時，每次劃分所取的基準就是當前無序區中關鍵字最小（或最大）的記錄，則快速排序所需的比較次數反而最多。
?
最好時間復雜度：在最好情況下，每次劃分所取的基準都是當前無序區的“中值”記錄，劃分的結果與基準的左、右兩個無序子區間的長度大致相等。總的關鍵字比較次數為?O(n×lgn)。
?
用遞歸樹來分析最好情況下的比較次數更簡單。因為每次劃分后左、右子區間長度大致相等，故遞歸樹的高度為?O(lgn),而遞歸樹每一層上各結點所對應的劃分過程中所需要的關鍵字比較次數總和不超過?n，故整個排序過程所需要的關鍵字比較總次數?C(n)=O(n×lgn)?。因為快速排序的記錄移動次數不大于比較的次數，所以快速排序的最壞時間復雜度應為?O(n^2 )，最好時間復雜度為?O(n×lgn)。
?
基準關鍵字的選取：在當前無序區中選取劃分的基準關鍵字是決定算法性能的關鍵。 ① “三者取中”的規則，即在當前區間里，將該區間首、尾和中間位置上的關鍵字比較，以三者之中值所對應的記錄作為基準，在劃分開始前將該基準記錄和該區的第?1?個記錄進行交換，此后的劃分過程與上面所給的?Partition?算法完全相同。 ② 取位于?low?和?high?之間的隨機數?k(low<=k<=high),?用?R[k]?作為基準；選取基準最好的方法是用一個隨機函數產生一個位于?low?和?high?之間的隨機數?k(low<=k<=high),?用?R[k]?作為基準?,?這相當于強迫?R[low..high]?中的記錄是隨機分布的。用此方法所得到的快速排序一般稱為隨機的快速排序。隨機的快速排序與一般的快速排序算法差別很小。但隨機化后，算法的性能大大提高了，尤其是對初始有序的文件，一般不可能導致最壞情況的發生。算法的隨機化不僅僅適用于快速排序，也適用于其他需要數據隨機分布的算法。
?
平均時間復雜度：盡管快速排序的最壞時間為?O(n^2 ),?但就平均性能而言，它是基于關鍵字比較的內部排序算法中速度最快的，快速排序亦因此而得名。它的平均時間復雜度為?O(n×lgn)。
?
空間復雜度：快速排序在系統內部需要一個棧來實現遞歸。若每次劃分較為均勻，則其遞歸樹的高度為?O(lgn),?故遞歸后所需棧空間為?O(lgn)?。最壞情況下，遞歸樹的高度為?O(n),?所需的棧空間為?O(n)?。
?
穩定性：快速排序是非穩定的。
總結
以上是生活随笔為你收集整理的快速排序和二分查找时间复杂度详解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： maven3实战之仓库(仓库搜索功能)
- 下一篇： 【云原生】什么是 CI/CD ？| 软件