1樓：匿名使用者
1.快速排序-時空複雜度：
快速排序每次將待排序陣列分為兩個部分，在理想狀況下，每一次都將待排序陣列劃分成等長兩個部分，則需要logn次劃分。
而在最壞情況下，即陣列已經有序或大致有序的情況下，每次劃分只能減少一個元素，快速排序將不幸退化為氣泡排序，所以快速排序時間複雜度下界為o(nlogn)，最壞情況為o(n^2)。在實際應用中，快速排序的平均時間複雜度為o(nlogn)。
快速排序在對序列的操作過程中只需花費常數級的空間。空間複雜度s(1)。
但需要注意遞迴棧上需要花費最少logn最多n的空間。
2.快速排序-隨機化演算法：
快速排序的實現需要消耗遞迴棧的空間，而大多數情況下都會通過使用系統遞迴棧來完成遞迴求解。在元素數量較大時，對系統棧的頻繁存取會影響到排序的效率。
一種常見的辦法是設定一個閾值，在每次遞迴求解中，如果元素總數不足這個閾值，則放棄快速排序，呼叫一個簡單的排序過程完成該子序列的排序。這樣的方法減少了對系統遞迴棧的頻繁存取，節省了時間的消費。
一般的經驗表明，閾值取一個較小的值，排序演算法採用選擇、插入等緊湊、簡潔的排序。一個可以參考的具體方案：閾值t=10，排序演算法用選擇排序。
閾值不要太大，否則省下的存取系統棧的時間，將會被簡單排序演算法較多的時間花費所抵消。
另一個可以參考的方法，是自行建棧模擬遞迴過程。但實際經驗表明，收效明顯不如設定閾值。
3.快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。
這樣在陣列已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的優化方法是隨機化演算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是o(n^2)，但最壞情況不再依賴於輸入資料，而是由於隨機函式取值不佳。
實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對於絕大多數輸入資料達到o(nlogn)的期望時間複雜度。一位前輩做出了一個精闢的總結：
「隨機化快速排序可以滿足一個人一輩子的人品需求。」
隨機化快速排序的唯一缺點在於，一旦輸入資料中有很多的相同資料，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間複雜度將毫無疑問的降低到o(n^2)。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。
4.設要排序的陣列是a[0]……a[n-1]，首先任意選取一個資料（通常選用第一個資料）作為關鍵資料，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。一趟快速排序的演算法是：
1）設定兩個變數i、j，排序開始的時候：i=0，j=n-1；
2）以第一個陣列元素作為關鍵資料，賦值給key，即 key=a[0]；
3）從j開始向前搜尋，即由後開始向前搜尋（j=j-1），找到第一個小於key的值a[j]，並與a[i]交換；
4）從i開始向後搜尋，即由前開始向後搜尋（i=i+1），找到第一個大於key的a[i]，與a[j]交換；
5）重複第3、4、5步，直到 i=j； (3,4步是在程式中沒找到時候j=j-1，i=i+1。找到並交換的時候i， j指標位置不變。另外當i=j這過程一定正好是i+或j+完成的最後另迴圈結束)
例如：待排序的陣列a的值分別是：（初始關鍵資料：x=49） 注意關鍵x永遠不變，永遠是和x進行比較，無論在什麼位子，最後的目的就是把x放在中間，小的放前面大的放後面。
a[0] 、 a[1]、 a[2]、 a[3]、 a[4]、 a[5]、 a[6]：
49 38 65 97 76 13 27
進行第一次交換後： 27 38 65 97 76 13 49
( 按照演算法的第三步從後面開始找)
進行第二次交換後： 27 38 49 97 76 13 65
( 按照演算法的第四步從前面開始找》x的值，65>49,兩者交換，此時：i=3 )
進行第三次交換後： 27 38 13 97 76 49 65
( 按照演算法的第五步將又一次執行演算法的第三步從後開始找
進行第四次交換後： 27 38 13 49 76 97 65
( 按照演算法的第四步從前面開始找大於x的值，97>49,兩者交換，此時：i=4,j=6 )
此時再執行第三步的時候就發現i=j，從而結束一趟快速排序，那麼經過一趟快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。
快速排序就是遞迴呼叫此過程——在以49為中點分割這個資料序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部資料序列的快速排序，最後把此資料序列變成一個有序的序列，根據這種思想對於上述陣列a的快速排序的全過程如圖6所示：
初始狀態
進行一次快速排序之後劃分為 49
分別對前後兩部分進行快速排序 經第三步和第四步交換後變成 完成排序。
經第三步和第四步交換後變成 完成排序。
2樓：孤竹寒武
快排的平均時間為：t(n) = k*n*lnn
時間複雜度為：o(n*logn)
快速排序法的平均時間複雜度是多少？
3樓：匿名使用者
平均時間複雜度是o(nlog2n).
4樓：匿名使用者
平均時間複雜度o（nlogn），最壞時間複雜度o（n*n）,輔助空間o（logn）
5樓：
nlog2n
n倍以2為底n的對數。
快速排序演算法在平均情況下的時間複雜度為 求詳解
6樓：匿名使用者
時間複雜度為o(nlogn) n為元素個數
1. 快速排序的三個步驟：
1.1. 找到序列中用於劃分序列的元素
1.2. 用元素劃分序列
1.3. 對劃分後的兩個序列重複1,2兩個步驟指導序列無法再劃分
所以對於n個元素其排序時間為
t(n) = 2*t(n/2) + n （表示將長度為n的序列劃分為兩個子序列，每個子序列需要t(n/2)
的時間，而劃分序列需要n的時間）
而 t(1) = 1 （表示長度為1的序列無法劃分子序列，只需要1的時間即可）
t(n) = 2^logn + logn * n （n被不斷二分最終只能二分logn次（最優的情況,每次選取
的元素都均分序列））
= n + nlogn
因此t(n) = o(nlogn)
以上是最優情況的推導，因此快速排序在最優情況下其排序時間為o(nlogn),通常平均情況
我們也認為是此值。
在最壞情況下其會退化為氣泡排序，t(n) = t(n - 1) + n (每次選取的元素只能將序列劃分為
一段，即自身是 最小元素或最大元素)
因此t(n) = n * (n-1) / 2 相當於o(n^2)
7樓：匿名使用者
時間複雜度為o（nlogn）n是多少元素
1。快速排序的三個步驟：
1.1。查詢序列用於劃分的序列中的元素
1.2元素劃分的序列
1.3 1,2兩個步驟的過程不斷重複，兩個序列劃分指導序列不能被細分
n個元素的排序條件為t（n）= 2 * t（n / 2個）+ n（表示序列分為兩個子序列中的n的長度，每個子序列需要到t（n / 2個）
時間除以
t（1）= 1（序列的長度不能被劃分為子序列，序列的n個）只需要1罐）
t（n）= 2 ^ logn + logn * n（n為不斷二分法最後只有兩點：logn（最佳，各選擇
平均序列的元素））
= n + nlogn
因此，t（n）= o（nlogn ）
以上是派生的理想情況下，快速排序排序在最佳的情況下，時間為o（nlogn）通常平均
我們也相信，這個值。
在最壞的情況下，它會淪為氣泡排序，t（n）= t（n - 1個）+ n（每次選擇元素序列分為
一些，這是他們自己的元素是最小的或最大的元素）
t（n）= n *（n-1）/ 2，相當於為o（n ^ 2）
8樓：雨的恩惠
正如歸併排序一樣，快速排序也是遞迴的，因此，他的分析需要求解一個遞推公式。我們將對快速排序進行這種分析，假設有一個隨機的樞紐元（不用三數中值分割法），對一些小的檔案也不使用截止範圍。和歸併排序一樣，取t(0)=t(1)=1,快速排序的執行時間等於兩個遞迴呼叫的執行時間加上花費在分割上的限行時間（樞紐元的選取僅花費常數時間）。
我們得到基本的快速排序關係：
t(n)=t(i)+t(n-i-1)+**
其中，i=|s1|是s1中的時間個數。我們還將考查三種情況。
最壞情況的分析：
樞紐元始終是最小元素。此時i=0，如果我們忽略無關緊要的 t(0)-1,那麼遞推關係為
t(n0=t(1)+c(sum+=i;i in (2,n])= o(n^2)
最好情況：
在最好的情況下，樞紐元正好位於中間，t(n)=o(n* log(n))
平均情況的分析：
t(n)=o(n*logn)
《資料結構與演算法分許（c語言描述）》 片段，字太多了，全是公式推導，打了一部分
9樓：郝霞佛念
快速排序時間複雜度下界為o(nlogn)，最壞情況為o(n^2)
快速排序的平均時間複雜度為o(nlogn)。
請問快速排序的時間複雜度是怎麼推算的？ 10
10樓：
每次分成兩段，那麼分的次數就是logn了哦，每一次處理需要n次計算，那麼時間複雜度就是nlogn了！
注意這是平均時間複雜度，因為你分的時候可能並不均勻！
根據平均情況來說是o(nlogn),因為在資料分佈等概率的情況下對於單個資料來說在logn次移動後就會被放到正確的位置上了。
最壞是o(n^2).這種情況就是陣列剛好的倒序，然後每次去中間元的時候都是取最大或者最小。
11樓：廉聽雲薄朝
歸併排序每次會把當前的序列一分為二，然後兩部分各自排好序之後再合併，這樣的話你可以手動模擬出一顆二叉樹來，每一層的總計算量是o(n)的，總的層數是o(logn)的，所以總的複雜度是nlogn
快速排序的複雜度怎麼算，是多少？
12樓：
這個，我確實一點也不懂，幫你搜尋。
1.快速排序-時空複雜度：
快速排序每次將待排序陣列分為兩個部分，在理想狀況下，每一次都將待排序陣列劃分成等長兩個部分，則需要logn次劃分。
而在最壞情況下，即陣列已經有序或大致有序的情況下，每次劃分只能減少一個元素，快速排序將不幸退化為氣泡排序，所以快速排序時間複雜度下界為o(nlogn)，最壞情況為o(n^2)。在實際應用中，快速排序的平均時間複雜度為o(nlogn)。
快速排序在對序列的操作過程中只需花費常數級的空間。空間複雜度s(1)。
但需要注意遞迴棧上需要花費最少logn最多n的空間。
2.快速排序-隨機化演算法：
快速排序的實現需要消耗遞迴棧的空間，而大多數情況下都會通過使用系統遞迴棧來完成遞迴求解。在元素數量較大時，對系統棧的頻繁存取會影響到排序的效率。
一種常見的辦法是設定一個閾值，在每次遞迴求解中，如果元素總數不足這個閾值，則放棄快速排序，呼叫一個簡單的排序過程完成該子序列的排序。這樣的方法減少了對系統遞迴棧的頻繁存取，節省了時間的消費。
一般的經驗表明，閾值取一個較小的值，排序演算法採用選擇、插入等緊湊、簡潔的排序。一個可以參考的具體方案：閾值t=10，排序演算法用選擇排序。
閾值不要太大，否則省下的存取系統棧的時間，將會被簡單排序演算法較多的時間花費所抵消。
另一個可以參考的方法，是自行建棧模擬遞迴過程。但實際經驗表明，收效明顯不如設定閾值。
3.快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。
這樣在陣列已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的優化方法是隨機化演算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是o(n^2)，但最壞情況不再依賴於輸入資料，而是由於隨機函式取值不佳。
實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對於絕大多數輸入資料達到o(nlogn)的期望時間複雜度。一位前輩做出了一個精闢的總結：
「隨機化快速排序可以滿足一個人一輩子的人品需求。」
隨機化快速排序的唯一缺點在於，一旦輸入資料中有很多的相同資料，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間複雜度將毫無疑問的降低到o(n^2)。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。
4.設要排序的陣列是a[0]……a[n-1]，首先任意選取一個資料（通常選用第一個資料）作為關鍵資料，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。一趟快速排序的演算法是：
1）設定兩個變數i、j，排序開始的時候：i=0，j=n-1；
2）以第一個陣列元素作為關鍵資料，賦值給key，即 key=a[0]；
3）從j開始向前搜尋，即由後開始向前搜尋（j=j-1），找到第一個小於key的值a[j]，並與a[i]交換；
4）從i開始向後搜尋，即由前開始向後搜尋（i=i+1），找到第一個大於key的a[i]，與a[j]交換；
5）重複第3、4、5步，直到 i=j； (3,4步是在程式中沒找到時候j=j-1，i=i+1。找到並交換的時候i， j指標位置不變。另外當i=j這過程一定正好是i+或j+完成的最後另迴圈結束)
例如：待排序的陣列a的值分別是：（初始關鍵資料：x=49） 注意關鍵x永遠不變，永遠是和x進行比較，無論在什麼位子，最後的目的就是把x放在中間，小的放前面大的放後面。
a[0] 、 a[1]、 a[2]、 a[3]、 a[4]、 a[5]、 a[6]：
49 38 65 97 76 13 27
進行第一次交換後： 27 38 65 97 76 13 49
( 按照演算法的第三步從後面開始找)
進行第二次交換後： 27 38 49 97 76 13 65
( 按照演算法的第四步從前面開始找》x的值，65>49,兩者交換，此時：i=3 )
進行第三次交換後： 27 38 13 97 76 49 65
( 按照演算法的第五步將又一次執行演算法的第三步從後開始找
進行第四次交換後： 27 38 13 49 76 97 65
( 按照演算法的第四步從前面開始找大於x的值，97>49,兩者交換，此時：i=4,j=6 )
此時再執行第三步的時候就發現i=j，從而結束一趟快速排序，那麼經過一趟快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。
快速排序就是遞迴呼叫此過程——在以49為中點分割這個資料序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部資料序列的快速排序，最
演算法排序的最低時間複雜度為什麼是O（nlogn）
這個首先要明確一點，只用到比較的排序演算法最低時間複雜度是o nlogn 而 內像桶排這樣的容只需要o r r為桶的大小 為了證明只用到比較的排序演算法最低時間複雜度是o nlogn 首先要引入決策樹。首先決策樹是一顆二叉樹，每個節點表示元素之間一組可能的排序，它予以京進行的比較相一致，比較的結果是...
設計n個數的排序演算法，並要求計算演算法複雜度
氣泡排序的演算法時間複雜度上o n 2 氣泡排序是這樣實現的 首先將所有待排序的數字放入工作列表中。從列表的第一個數字到倒數第二個數字，逐個檢查 若某一位上的數字大於他的下一位，則將它與它的下一位交換。重複2號步驟，直至再也不能交換。氣泡排序的平均時間複雜度與插入排序相同，也是平方級的，但也是非常容...
在快速排序，堆排序，歸併排序中哪個是最穩定的排序方法
1 快速排序 quicksort 快速排序是一個就地排序，分而治之，大規模遞迴的演算法。從本質上來說，它是歸併排序的就地版本。快速排序可以由下面四步組成。1 如果不多於1個資料，直接返回。2 一般選擇序列最左邊的值作為支點資料。3 將序列分成2部分，一部分都大於支點資料，另外一部分都小於支點資料。4...