02-從四個角度分析時間復雜度
最好和最壞時間復雜度
我們來分析下這兩端代碼
// n 表示陣列 array 的長度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) { // n
if (array[i] == x) pos = i;
}
return pos;
}
這個時間復雜度也是O(n),我們可以對上面這段代碼進行優化一下
// n 表示陣列 array 的長度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) { // n
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
從普通情況下分析,這個時間復雜度是O(n)
但是這樣并看不出區別,我們可以從兩種情況下進行分析
最壞情況下:整個陣列都沒有找到,那么代碼就會執行n次,時間復雜度就是O(n);
最好情況下:第一次就找到了,退出回圈,那么回圈只執行一次,時間復雜度就是O(1);
所以我們可以看出,在不同情況下,時間復雜度是不一樣的
平均復雜時間度
從上段代碼可以看出,我們都知道，最好情況時間復雜度和最壞情況時間復雜度對應的都是極端情況下的代碼復雜度，發生的概率其實并不大，為了更好地表示平均情況下的復雜度，平均時間復雜度的概念就出來了
我們繼續拿上面這段代碼進行分析,總共有n+1種情況,分為在陣列中找到和沒在陣列中找到
我們在細分下在陣列中找到的情況總和,有n種情況,因為在索引(0~n-1)中都有可能找到
所以我們把陣列中找到的和在陣列中沒找到的情況 總共有 n+1種情況
將在陣列中找到的每種情況下查找需要遍歷的元素的個數進行相加 和 在陣列中沒找到的情況下 一起相加 除以 (n+1)中情況
(1+2+3+4+5+6+...+n)+n/n+1
打括號的根據 等引數列公式
\[Sn=n\frac{({a1}+{a2})}{2} \]我們可以算出化簡過后的公式
\[\frac{n^2+3n}{2(n+1)} \]這就是我們細分過后所產生的時間復雜度,但是我們用大O表示法表示,其大O時間復雜度為O(n)
但是我們這么分析是有點問題的,并沒有把每種概率都考慮進去
假設在陣列中找到和沒在陣列中找到的概率分別是1/2
而在陣列中找到的概率為1/n,因為在(0~n-1)內每個索引都有可能找到
而沒在陣列中找到,一定是在陣列中找了n次的
我們對概率進行一個相加
\[1*\frac{1}{2n}+2*\frac{1}{2n}+....+n*\frac{1}{2n}+n*\frac12 \]計算出來的結果為:
\[\frac {3n+1}{4} \]這個值就是概率論中的加權平均值，也叫作期望值，所以平均時間復雜度的全稱應該叫加權平均時間復雜度或者期望時間復雜度，
只有同一塊代碼在不同的情況下，時間復雜度有量級的差距，我們才會使用這三種復雜度(最好,最壞,平均)表示法來區分，所以大家不需要擔心
均攤時間復雜度
我們還是依照慣例,先來分析一段代碼
// array 表示一個長度為 n 的陣列
// 代碼中的 array.length 就等于 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;
}
這個代碼執行分為兩種情況
- 陣列中有空閑,插入了資料
- 陣列中沒空閑,對陣列中所有數進行了一個相加求和
最好的情況下,就是陣列中有空閑,插入完就結束了,時間復雜度是O(1),
最壞的情況下,開始對陣列中進行求和,大家看那個for回圈,時間復雜度是O(n)
那平均時間復雜度是啥呢,我們可以繼續來算,答案會非常神奇,總情況數有 (n+1)種
概率發生都是一樣的,其實都是1/n+1
因為有n+1種情況下,進行一個相乘,發現概率是就是1,所以時間復雜度就是O(1)
首先，find() 函式在極端情況下，復雜度才為 O(1)，但 insert() 在大部分情況下，時間復雜度都為 O(1)，只有個別情況下，復雜度才比較高，為 O(n)，這是 insert()第一個區別于 find() 的地方，
我們再來看第二個不同的地方，對于 insert() 函式來說，O(1) 時間復雜度的插入和 O(n) 時間復雜度的插入，出現的頻率是非常有規律的，而且有一定的前后時序關系，一般都是一個 O(n) 插入之后，緊跟著 n-1 個 O(1) 的插入操作，回圈往復，
所以，針對這樣一種特殊場景的復雜度分析，我們并不需要像之前講平均復雜度分析方法那樣，找出所有的輸入情況及相應的發生概率，然后再計算加權平均值，
針對這種特殊的場景，我們引入了一種更加簡單的分析方法：攤還分析法，通過攤還分析得到的時間復雜度我們起了一個名字，叫均攤時間復雜度，
我們還是繼續看在陣列中插入資料的這個例子，每一次 O(n) 的插入操作，都會跟著 n-1 次 O(1) 的插入操作，所以把耗時多的那次操作均攤到接下來的 n-1 次耗時少的操作上，均攤下來，這一組連續的操作的均攤時間復雜度就是 O(1)
本文來自博客園，作者：CodeSpirit，轉載請注明原文鏈接：https://www.cnblogs.com/codespirit-zx/p/15303072.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/300863.html
標籤：其他