1樓：匿名使用者
什麼情況下的時間複雜度，平均效能？最壞？最好？
平均最好的是快速排序，最壞情況下最好的看是記錄移動和關鍵字比較哪個佔主導，最好時最低的是氣泡排序
2樓：笪星嚴冷珍
最好是o(n)，這個時候陣列本身已經是排好序的
平均情況和最差都是o(n^2)
以下排序演算法最壞情況下時間複雜度最低的是 a.氣泡排序 b.插入 c.選擇 d.快排
3樓：木頭釋然
在氣泡排序，插入排序，選擇排序，快速排序中，在最最壞情況下，快速排序的時間複雜為o(n2) ，插入排序o(n2)，選擇排序o(n2)，氣泡排序o(n2)。所以abcd時間複雜度是一樣的。
在快速排序演算法中，最為關鍵的就是選取一個基值，將陣列分為大於基值以及小於基值兩部分，並返回基值所以在位置以利用於遞迴劃分。
對陣列a，設需要劃分的其中一段為a[p]~a[r]，我們期待的結果是得到一個q，其中p<=q<=r，使得a[p]~a[q-1]<=a[q]<=a[q+1]~a[r]，這個時候原先的一段陣列被分成了三部分。
首先，設基值為這段陣列的最後一個元素a[r]，我們希望最後得到的結果是a[r]現在對應的值在演算法結束後可以排在比他大和小的兩部分的中間愛。
然後令i=p-1; j=p，當發現有a[j]>x時，j繼續前進，不需要任何移動。當發現a[j]<=x時，我們需要將這個元素放到小於基值的一邊，於是將i自加1，並交換此時a[i]，與a[j]的元素，然後j自加1。這個時候i指向的是比基值小的那段資料的最後一個元素，j指向的是第一個還沒有判斷的剩餘元素。
上面一步不斷迴圈直到j指向了r，此時只剩下r沒有和基值判斷了，而a[r]本來就是基值，而除了a[r]以外，a[p]~a[i]是小於基值的部分，a[i+1]~a[r-1]是大於基值的部分，所以此時只需交換a[i+1]和a[r]即可。
由於對陣列a從頭到尾掃描一次就可以得到結果，因此這一部分演算法複雜度為o(n)
4樓：匿名使用者
1.選擇排序：不穩定，時間複雜度 o(n^2)
選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將l[i..n]中最小者與l[i]交換位置。這樣，經過i遍處理之後，前i個記錄的位置已經是正確的了。
2.插入排序：穩定，時間複雜度 o(n^2)
插入排序的基本思想是，經過i-1遍處理後,l[1..i-1]己排好序。第i遍處理僅將l[i]插入l[1..
i-1]的適當位置，使得l[1..i] 又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。
首先比較l[i]和l[i-1]，如果l[i-1]≤ l[i]，則l[1..i]已排好序，第i遍處理就結束了；否則交換l[i]與l[i-1]的位置，繼續比較l[i-1]和l[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得l[j] ≤l[j+1]時為止。圖1演示了對4個元素進行插入排序的過程，共需要(a),(b),(c)三次插入。
3.氣泡排序：穩定，時間複雜度 o(n^2)
氣泡排序方法是最簡單的排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的「氣泡」，較小的元素比較輕，從而要往上浮。在氣泡排序演算法中我們要對這個「氣泡」序列處理若干遍。
所謂一遍處理，就是自底向上檢查一遍這個序列，並時刻注意兩個相鄰的元素的順序是否正確。如果發現兩個相鄰元素的順序不對，即「輕」的元素在下面，就交換它們的位置。顯然，處理一遍之後，「最輕」的元素就浮到了最高位置；處理二遍之後，「次輕」的元素就浮到了次高位置。
在作第二遍處理時，由於最高位置上的元素已是「最輕」元素，所以不必檢查。一般地，第i遍處理時，不必檢查第i高位置以上的元素，因為經過前面i-1遍的處理，它們已正確地排好序。
4.堆排序：不穩定，時間複雜度 o(nlog n)
堆排序是一種樹形選擇排序，在排序過程中，將a[n]看成是完全二叉樹的順序儲存結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關係來選擇最小的元素。
5.歸併排序：穩定，時間複雜度 o(nlog n)
設有兩個有序（升序）序列儲存在同一陣列中相鄰的位置上，不妨設為a[l..m]，a[m+1..h]，將它們歸併為一個有序數列，並儲存在a[l..h]。
6.快速排序：不穩定，時間複雜度 最理想 o(nlogn) 最差時間o(n^2)
快速排序是對氣泡排序的一種本質改進。它的基本思想是通過一趟掃描後，使得排序序列的長度能大幅度地減少。在氣泡排序中，一次掃描只能確保最大數值的數移到正確位置，而待排序序列的長度可能只減少1。
快速排序通過一趟掃描，就能確保某個數（以它為基準點吧）的左邊各數都比它小，右邊各數都比它大。然後又用同樣的方法處理它左右兩邊的數，直到基準點的左右只有一個元素為止。
幾種排序的時間複雜度，可以參考一下
5樓：匿名使用者
這幾個的最壞情況下的時間複雜度都是一樣的，一定要比較的話快排比較快，但氣泡排序比較穩定，最壞的話都是一樣的
6樓：匿名使用者
顯然都一樣，如果論平均時間就是快排最快o(nlogn)，其餘的都是o(n^2)，但快排最壞時間也是o(n^2)
7樓：匿名使用者
最壞的情況下好像都是n^2吧。
什麼排序的速度（時間複雜度）最快？
8樓：百度使用者
從時間複雜度看，所有內部排序方法可以分為兩類。
1.插入排序 選擇排序 起泡排序
其時間複雜度為o(n2)；
2.堆排序 快速排序 歸併排序
其時間複雜度為o(nlog2n)。
這是就平均情況而言的，如果從最好的情況考慮，則插入排序和起泡排序的時間複雜度最好，為o(n)，而其他演算法的最好情況同平均情況大致相同。
如果從最壞的情況考慮，快速排序的時間複雜度為o(n2)，插入排序和起泡排序雖然同平均情況相同，但係數大約增加一倍，執行速度降低一半，而選擇排序、堆排序和歸併排序則影響不大。
總之，在平均情況下，快速排序最快；
在最好情況下，插入排序和起泡排序最快；
在最壞情況下，堆排序和歸併排序最快。
9樓：匿名使用者
記序排序時間複雜度只要o(nlogn)
10樓：呵呵俠
桶排序o(n)瞭解一下
幾種排序的時間複雜度
11樓：我不是他舅
氣泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重複2號步驟，直至再也不能交換。
氣泡排序的平均時間複雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設陣列記憶體放了n個待排數字，陣列下標從1開始，到n結束。
i=1從陣列的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間複雜度也是o(n^2)的。
幾種排序以及其時間複雜度
12樓：我不是他舅
氣泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的專第一個數字到屬倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重複2號步驟，直至再也不能交換。
氣泡排序的平均時間複雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設陣列記憶體放了n個待排數字，陣列下標從1開始，到n結束。
i=1從陣列的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間複雜度也是o(n^2)的。
〔演算法〕排序的最低時間複雜度為什麼是o（nlogn）
13樓：匿名使用者
這個首先要明確一點，只用到比較的排序演算法最低時間複雜度是o(nlogn)，而
內像桶排這樣的容只需要o(r)(r為桶的大小)
為了證明只用到比較的排序演算法最低時間複雜度是o(nlogn)，首先要引入決策樹。
首先決策樹是一顆二叉樹，每個節點表示元素之間一組可能的排序，它予以京進行的比較相一致，比較的結果是樹的邊。
先來說明一些二叉樹的性質，令t是深度為d的二叉樹，則t最多有2^片樹葉。
具有l片樹葉的二叉樹的深度至少是logl。
所以，對n個元素排序的決策樹必然有n!片樹葉（因為n個數有n!種不同的大小關係），所以決策樹的深度至少是log(n!)，即至少需要log(n!)次比較。
而log(n!)=logn+log(n-1)+log(n-2)+...+log2+log1
>=logn+log(n-1)+log(n-2)+...+log(n/2)
>=(n/2)log(n/2)
>=(n/2)logn-n/2
=o(nlogn)
所以只用到比較的排序演算法最低時間複雜度是o(nlogn)。
14樓：超級慢
時間複雜度通常括號裡面的是頻度,就是該語句重複的次數一般情況下只需選擇一種基本操作來討論演算法的時間複雜度nlogn就是指執行的次數
具體怎麼個意思也不是太懂 數學學習的不好
連logn都忘記了....
C語言寫程式時出現的時間複雜度具體是什麼意思
資料結構沒學吧 演算法的執行時間依賴於具體的軟硬體環境，所以，不能用執行時間的長短來衡量演算法的時間複雜度，而要通過基本語句執行次數的數量級來衡量。求解演算法的時間複雜度的具體步驟是 找出演算法中的基本語句 演算法中執行次數最多的那條語句就是基本語句，通常是最內層迴圈的迴圈體。計算基本語句的執行次數...
快速排序方法的時間複雜度為on2nn
1 對於你的問題簡單解釋如下 理論計算機研究中，衡量演算法一般從兩個方面分析 時間複雜度和空間複雜度。空間複雜度跟時間複雜度是類似的，下面簡單解釋一下時間複雜度 對於一個資料規模為n的問題，解決該問題的演算法所用時間可以用含有n的函式t n 來表示。對於絕大多數情況，我們只需要瞭解演算法的一般效能而...
c 語言快速排序最好情況時間複雜度為什麼是 nlog2n
快速排序最好的情況是每次把上一次的陣列平均分成兩個子陣列。設陣列總數一共為n，如果把這n個數每次分成2半最後每個陣列只包含一個元素，假設要分k次，則2的k次方 n，解得k log2 n log以2為底對n取對數 也就是說要分log2 n次，而每次都是處理n個資料。所以總的時間複雜度為o n log2...