復雜度
復雜度分析
- 資料結構和演算法的目標：快、省，即執行效率和資源消耗
- “事后統計法”具有很大局限性，提前預估效率很重要
- 復雜度分析是學習演算法的精髓和分析演算法的利器
時間復雜度
- 假設每行代碼執行時間意義，所有代碼的執行時間
T(n)和每行代碼的執行次數n成正比，
T(n) = O (f(n))
- 大O時間復雜度表示代碼執行效率隨資料規模增長的變化趨勢，也叫漸進時間復雜度，
- 當n很大時，低階、常量、系數并不左右增長趨勢，可以省略，只需要記錄最大量級，
- 只關注回圈次數最多的一段代碼.
- 加法法則：總復雜度等于量級最大的那一段代碼，
- 乘法法則：嵌套代碼的復雜度等于內外代碼復雜度之積，
- 常見復雜度量級
- 非多項式量級：\(O(2^n),O(n!)\),稱為NP演算法，效率較低，
- 多項式量級：\(O(1),O(logn),O(n),O(nlogn),O(n^k)\)，
\(O(1)\)
int i = 1 ;
int j = 2 ;
int sum = i + j ;
常量級時間復雜度的表示方法，即便有 3 行，也是 O(1) ,并非 O(3) ，一般情況下，只要不存在回圈、遞回，復雜度都為 O(1) ，與代碼量無關，
\(O(logn)、O(nlogn)\)
int i = 1 ;
while ( i <= n )
{
i = i * 2 ;
}
這段代碼的復雜度為 \(O(log_2n)\)，不同底數的對數可以互相轉換，系數可以省略，所以統一表示為 \(O(logn)\)，
\(O(nlogn)\) 表示把 \(O(logn\)) 的代碼回圈執行n遍，
\(O(n+m)、O(n*m)\)
T1(n) + T2(m) = O (f(n) + g(m))
T1(n) * T2(m) = O (f(n) * g(m))
當有多個資料規模，表示復雜度時不能省略，
空間復雜度
- 大 O 空間復雜度表示代碼存盤空間隨資料規模增長的變化趨勢，也叫漸空間間復雜度，
void print(int n)
{
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i)
{
a[i] = i * i;
}
}
int[] a = new int[n]申請了大小為 n 的 int 型別陣列，忽略常量階的空間申請，所以上述代碼空間復雜度為 O(n)，- 常見的空間復雜度有\(O(1),O(n),O(n^2)\);
最好、最壞情況時間復雜度
public int find(int[] array,int n,int x)
{
int p = -1 ;
for(int i = 0 ; i < n ; ++i)
{
if(array[i] == x)
{
p = i ;
break ;
}
}
return p ;
}
/**
上述代碼的作用是回傳陣列中 x 出現的位置，
最好：第一個就是要找-> O(1)
最壞：遍歷整個陣列沒有找到該元素-> O(n)
**/
- 最好情況時間復雜度
最理想情況下，執行這段代碼的時間復雜度，
- 最壞情況時間復雜度
最糟糕情況下，執行這段代碼的時間復雜度，
平均時間復雜度
\[\frac{1+2+3+...+n+n}{n+1}\quad=\quad\frac{n(n+3)}{2(n+1)} \]分析上述代碼，在長度為n的陣列中查詢x的位置，有 n+1 種情況，分別為陣列的 0 到 n-1 位置上和不在陣列中，把每種情況下，需要遍歷的元素個數累加起來，除以 n+1 ，得到需要遍歷元素個數的平均值，
忽略常量、系數、低階，簡化后時間復雜度為O(n);結果雖然正確，但是這樣計算沒有考慮每種情況發生的概率，正確計算程序如下：
\[1*\frac{1}{2n}+2*\frac{1}{2n}+...+n*\frac{1}{2n}+n*\frac{1}{2}=\frac{3n+1}{4} \]此結果是加權平均值，平均時間復雜度即加權平均時間復雜度，簡化后得 O(n)，
均攤時間復雜度
int[] array = new int[n];
int count = 0;
void insert(int val)
{
if (count == array.length)
{
int sum = 0;
for (int i = 0; i < array.length; ++i)
{
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
這段代碼實作了一個往陣列中插入資料的功能，當陣列滿了之后，即 count == array.length 時，用 for 回圈遍歷陣列求和，將求和之后的 sum 值放到陣列的第一個位置，然后從第二個 位置開始插入資料，如果陣列一開始就有空閑空間，則直接將資料插入陣列
分析以上代碼，得出：
- 最好情況時間復雜度：有空閑位置，直接插入下標為 count 的位置，復雜度為 O(1)
- 最壞情況時間復雜度：遍歷陣列，復雜度為 O(n)
- 加權平均時間復雜度：有空閑位置 n 種情況，不空閑 1 種，概率都為\(\frac{1}{n+1}\)，加權平均時間復雜度為 O(1)
-
均攤時間復雜度是用攤還分析法得出的：
例如上述代碼中，每一次 O(n) 的插入操作，都會緊跟 n-1 個 O(1) 的插入操作，把耗時多的操作均攤到接下來 O(1) 的操作上，那么這一組操作的均攤時間復雜度就是 O(1)
對一個資料結構進行一組連續操作中，大部分情況下時間復雜度都很低，只有個別情況下時間復雜度比較高，而且這些操作之間存在前后連貫的時序關系，這個時候，我們可以將這一組操作放在一起分析，看是否能將較高時間復雜度那次操作的耗時，平攤到其他那些時間復雜度比較低的操作上，
在能夠應用均攤時間復雜度分析的場合，一般均攤時間復雜度就等于最好情況時間復雜度
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/91959.html
標籤：其他
上一篇：什么是堆疊？