1、常見的排序演算法
2、演算法的時間復雜度
時間頻度和時間復雜度
時間頻度T(n)
一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測驗才能知道，但我們不可能也沒有必要對每個演算法都上機測驗，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了，并且一個演算法花費的時間與演算法中陳述句的執行次數成正比例，哪個演算法中陳述句執行次數多，它花費時間就多，一個演算法中的陳述句執行次數稱為陳述句頻度或時間頻度，記為T(n)，
時間復雜度O(n)
一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函式，用T(n)表示，若有某個輔助函式f(n),使得當n趨近于無窮大時，T（n)/f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函式，記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度，
在T(n)=4n2-2n+2中，就有f(n)=n2，使得T（n)/f(n)的極限值為4，那么O(f(n))，也就是時間復雜度為O(n2)
-
對于不是只有常數的時間復雜度忽略時間頻度的系數、低次項常數
-
對于只有常數的時間復雜度，將常數看為1
常見的時間復雜度
常數階 O(1)
int i = 1; i++;
無論代碼執行了多少行，只要沒有回圈等復雜的結構，時間復雜度都是O(1)
對數階O(log2n)
while(i<n) {
i = i*2;
}
此處i并不是依次遞增到n，而是每次都以倍數增長，假設回圈了x次后i大于n，則2x = n，x=log2n
線性階O(n)
for(int i = 0; i<n; i++) {
i++;
}
這其中，回圈體中的代碼會執行n+1次，時間復雜度為O(n)
線性對數階O(nlog2n)
for(int i = 0; i<n; i++) {
j = 1;
while(j<n) {
j = j*2;
}
}
此處外部為一個回圈，回圈了n次，內部也是一個回圈，但內部f回圈的時間復雜度是log2n
所以總體的時間復雜度為線性對數階O(nlog2n)
平方階O(n2)
for(int i = 0; i<n; i++) {
for(int j = 0; j<n; j++) {
//回圈體
}
}
立方階O(n3)
for(int i = 0; i<n; i++) {
for(int j = 0; j<n; j++) {
for(int k = 0; k<n; k++) {
//回圈體
}
}
}
可以看出平方階、立方階的復雜度主要是否回圈嵌套了幾層來決定的
3、排序演算法的時間復雜度
| 排序演算法 | 平均時間 | 最差時間 | 穩定性 | 空間復雜度 | 備注 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | 穩定 | O(1) | n較小時好 |
| 交換排序 | O(n2) | O(n2) | 不穩定 | O(1) | n較小時好 |
| 選擇排序 | O(n2) | O(n2) | 不穩定 | O(1) | n較小時好 |
| 插入排序 | O(n2) | O(n2) | 穩定 | O(1) | 大部分已有序時好 |
| 基數排序 | O(n*k) | O(n*k) | 穩定 | O(n) | 二維陣列（桶）、一維陣列（桶中首元素的位置） |
| 希爾排序 | O(nlogn) | O(ns)(1<s<2) | 不穩定 | O(1) | s是所選分組 |
| 快速排序 | O(nlogn) | O(n2) | 不穩定 | O(logn) | n較大時好 |
| 歸并排序 | O(nlogn) | O(nlogn) | 穩定 | O(1) | n較大時好 |
| 堆排序 | O(nlogn) | O(nlogn) | 不穩定 | O(1) | n較大時好 |
本文來自博客園，作者：腹白，轉載請注明原文鏈接：https://www.cnblogs.com/wyh518/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/511059.html
標籤：其他
上一篇：汽車安全困境：如何破局？
下一篇：Bert不完全手冊9. 長文本建模 BigBird & Longformer & Reformer & Performer