?

一個算法的優劣往往通過算法復雜度來衡量，算法復雜度包括時間復雜度和空間復雜度。

時間復雜度是算法的所需要消耗的時間，時間越短，算法越好。可以對算法的代碼進行估計，而得到算法的時間復雜度。

一般來說，算法代碼簡短精悍可以用來減少算法的時間復雜度！

?

空間復雜度指的是算法程序在執行時所需要的存儲空間。空間復雜度可以分為以下兩個方面！

1.程序的保存所需要的存儲空間資源。即程序的大小；

2.程序在執行過程中所需要消耗的存儲空間資源，如中間變量等；

一般來說，程序的大小越小，執行過程中消耗的資源越少，這個程序就越好！

下面為時間復雜度和空間復雜度的計算

時間復雜度是總運算次數表達式中受n的變化影響最大的那一項(不含系數) 比如：一般總運算次數表達式類似于這樣： a*2n+b*n3+c*n2+d*n*lg(n)+e*n+f a ！ =0時，時間復雜度就是O(2n); a=0,b<>0 =>O(n3); a,b=0,c<>0 =>O(n2)依此類推 例子: (1) for(i=1;i<=n;i++) //循環了n*n次，當然是O(n2)for(j=1;j<=n;j++)s++; (2) for(i=1;i<=n;i++)//循環了(n+n-1+n-2+...+1)≈(n2)/2，因為時間復雜度是不考慮系數的，所以也是O(n2)for(j=i;j<=n;j++)s++; (3) for(i=1;i<=n;i++)//循環了(1+2+3+...+n)≈(n^2)/2,當然也是O(n2)for(j=1;j<=i;j++)s++; (4) i=1;k=0;//循環了n-1≈n次，所以是O(n)while(i<=n-1){k+=10*i; i++; } (5) for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1; // 循環了(1 ²+2 ²+3 ²+...+n ²)=n(n+1)(2n+1)/6(這個公式要記住哦)≈(n ³)/3，不考慮系數，自然是O(n ³) 另外，在時間復雜度中，log ₂n與lg(n)(同lg ₁₀(n))是等價的，因為對數換底公式： log _ab=log _cb/log _ca 所以，log ₂n=log ₂10 * lg(n),忽略掉系數，二者當然是等價的 二、計算方法 1.一個算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。
但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。
并且一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。 一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。 2.一般情況下，算法的基本操作重復執行的次數是模塊n的某一個函數f（n），
因此，算法的時間復雜度記做：T（n）=O（f（n））。隨著模塊n的增大，算法執行的時間的增長率和f（n）的增長率成正比，
所以f（n）越小，算法的時間復雜度越低，算法的效率越高。 在計算時間復雜度的時候，先找出算法的基本操作，然后根據相應的各語句確定它的執行次數，
再找出T（n）的同數量級（它的同數量級有以下：1，Log ₂n ，n ，nLog ₂n ，n的平方，n的三次方，2的n次方，n！），
找出后，f（n）=該數量級，若T(n)/f(n)求極限可得到一常數c，則時間復雜度T（n）=O（f（n））。 3.常見的時間復雜度 按數量級遞增排列，常見的時間復雜度有： 常數階O(1), 對數階O(log ₂n), 線性階O(n), 線性對數階O(nlog ₂n), 平方階O(n ²)，
立方階O(n ³),...， k次方階O(n ^k), 指數階O(2 ⁿ) 。 其中， 1.O(n)，O(n ²)， 立方階O(n ³),...， k次方階O(n ^k) 為多項式階時間復雜度，分別稱為一階時間復雜度，二階時間復雜度。。。。 2.O(2 ⁿ)，指數階時間復雜度，該種不實用 3.對數階O(log ₂n), 線性對數階O(nlog ₂n)，除了常數階以外，該種效率最高 例：算法：for（i=1;i<=n;++i）{for(j=1;j<=n;++j){c[ i ][ j ]=0; //該步驟屬于基本操作 執行次數：n ² for(k=1;k<=n;++k)c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬于基本操作 執行次數：n ³ }}則有 T（n）= n ²+n ³，根據上面括號里的同數量級，我們可以確定 n ³為T（n）的同數量級則有f（n）= n ³，然后根據T（n）/f（n）求極限可得到常數c則該算法的 時間復雜度：T（n）=O（n ³) 四、定義：
如果一個問題的規模是n，解這一問題的某一算法所需要的時間為T(n)，它是n的某一函數 T(n)稱為這一算法的“時間復雜性”。 當輸入量n逐漸加大時，時間復雜性的極限情形稱為算法的“漸近時間復雜性”。 我們常用大O表示法表示時間復雜性，注意它是某一個算法的時間復雜性。大O表示只是說有上界，由定義如果f(n)=O(n)，那顯然成立f(n)=O(n^2)，它給你一個上界，但并不是上確界，但人們在表示的時候一般都習慣表示前者。 此外，一個問題本身也有它的復雜性，如果某個算法的復雜性到達了這個問題復雜性的下界，那就稱這樣的算法是最佳算法。 “大O記法”：在這種描述中使用的基本參數是 n，即問題實例的規模，把復雜性或運行時間表達為n的函數。這里的“O”表示量級 (order)，比如說“二分檢索是 O(logn)的”,也就是說它需要“通過logn量級的步驟去檢索一個規模為n的數組”記法 O ( f(n) )表示當 n增大時，運行時間至多將以正比于 f(n)的速度增長。 這種漸進估計對算法的理論分析和大致比較是非常有價值的，但在實踐中細節也可能造成差異。
例如，一個低附加代價的O(n2)算法在n較小的情況下可能比一個高附加代價的 O(nlogn)算法運行得更快。
當然，隨著n足夠大以后，具有較慢上升函數的算法必然工作得更快。 O(1) Temp=i;i=j;j=temp; 以上三條單個語句的頻度均為1，該程序段的執行時間是一個與問題規模n無關的常數。
算法的時間復雜度為常數階，記作T(n)=O(1)。如果算法的執行時間不隨著問題規模n的增加而增長，
即使算法中有上千條語句，其執行時間也不過是一個較大的常數。此類算法的時間復雜度是O(1)。 O(n ²)
1) 交換i和j的內容
sum=0； （一次）
for(i=1;i<=n;i++) （n次 ）
for(j=1;j<=n;j++) （n ²次 ）
sum++； （n^2次 ）
解：T(n)=2n^2+n+1 =O(n^2) 2)
for (i=1;i<n;i++) {
y=y+1; //頻度是n-1
for (j=0;j<=(2*n);j++)
x++; //頻度是(n-1)*(2n+1)=2n ²-n-1
}
　　　　f(n)=2n ²-n-1+(n-1)=2n ²-2 該程序的時間復雜度T(n)=O(n ²). O(n)
3)
a=0; b=1; //頻度：2
for (i=1;i<=n;i++) //頻度： n
{
s=a+b;　　　　//頻度： n-1
　b=a;　　　　　//頻度：n-1
a=s;　　　　　//頻度：n-1
}
T(n)=2+n+3(n-1)=4n-1=O(n).

O(log ₂n )
4)
i=1; //頻度是1
　　 while (i<=n)
i=i*2; //頻度是f(n),
則：2 ^f(n)<=n;f(n)<=log ₂n 取最大值f(n)= log ₂n, T(n)=O(log ₂n ) O(n ³) 5)
for(i=0;i<n;i++) {
for(j=0;j<i;j++) {
for(k=0;k<j;k++)
x=x+2;
}
}
解：當i=m, j=k的時候,內層循環的次數為k當i=m時, j 可以取 0,1,...,m-1 , 所以這里最內循環共
進行了0+1+...+m-1=(m-1)m/2次所以,i從0取到n, 則循環共進行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6
所以時間復雜度為O(n ³). 我們還應該區分算法的最壞情況的行為和期望行為。如快速排序的最壞情況運行時間是 O(n ²)，
但期望時間是 O(nlogn)。通過每次都仔細 地選擇基準值，我們有可能把平方情況 (即O(n ²)情況)
的概率減小到幾乎等于 0。在實際中，精心實現的快速排序一般都能以 (O(nlogn)時間運行。
下面是一些常用的記法：訪問數組中的元素是常數時間操作，或說O(1)操作。一個算法如 果能在每個步驟去掉一半數據元素，
如二分檢索，通常它就取 O(logn)時間。用strcmp比較兩個具有n個字符的串需要O(n)時間。
常規的矩陣乘算法是O(n ³)，因為算出每個元素都需要將n對 元素相乘并加到一起，所有元素的個數是n ²。
指數時間算法通常來源于需要求出所有可能結果。例如，n個元 素的集合共有2n個子集,所以要求出
所有子集的算法將是O(2n)的。指數算法一般說來是太復雜了，除非n的值非常小，因為，在 這個問題
中增加一個元素就導致運行時間加倍。不幸的是，確實有許多問題 (如著名的“巡回售貨員問題” )，
到目前為止找到的算法都是指數的。如果我們真的遇到這種情況，通常應該用尋找近似最佳結果的算法替代之。

?二.空間復雜度

空間復雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。
一個算法在計算機存儲器上所占用的存儲空間，
包括程序代碼所占用的空間，輸入數據所占用的空間和輔助變量所占用的空間這三個方面。
算法的輸入輸出數據所占用的存儲空間是由要解決的問題決定的，是通過參數表由調用函數傳遞而來的，
它不隨本算法的不同而改變。存儲算法本身所占用的存儲空間與算法書寫的長短成正比，要壓縮這方面的存儲空間，
就必須編寫出較短的算法。算法在運行過程中臨時占用的存儲空間隨算法的不同而異，有的算法只需要占用少量的臨時工作單元，
而且不隨問題規模的大小而改變，我們稱這種算法是“就地"進行的，是節省存儲的算法，如這些介紹過的幾個算法都是如此；
有的算法需要占用的臨時工作單元數與解決問題的規模n有關，它隨著n的增大而增大，當n較大時，將占用較多的存儲單元，
例如將在第九章介紹的快速排序和歸并排序算法就屬于這種情況。分析一個算法所占用的存儲空間要從各方面綜合考慮。如對于遞歸算法來說，一般都比較簡短，算法本身所占用的存儲空間較少，但運行時需要一個附加堆棧，從而占用較多的臨時工作單元；若寫成非遞歸算法，一般可能比較長，算法本身占用的存儲空間較多，但運行時將可能需要較少的存儲單元。一個算法的空間復雜度只考慮在運行過程中為局部變量分配的存儲空間的大小，它包括為參數表中形參變量分配的存儲空間和為在函數體中定義的局部變量分配的存儲空間兩個部分。若一個算法為遞歸算法，其空間復雜度為遞歸所使用的堆棧空間的大小，它等于一次調用所分配的臨時存儲空間的大小乘以被調用的次數(即為遞歸調用的次數加1，這個1表不開始進行的一次非遞歸調用)。算法的空間復雜度一般也以數量級的形式給出。如當一個算法的空間復雜度為一個常量，即不隨被處理數據量n的大小而改變時，可表示為O(1)；當一個算法的空間復雜度與以2為底的n的對數成正比時，可表示為0(log ₂n)；當一個算法的空I司復雜度與n成線性比例關系時，可表示為0(n).若形參為數組，則只需要為它分配一個存儲由實參傳送來的一個地址指針的空間，即一個機器字長空間；若形參為引用方式，則也只需要為其分配存儲一個地址的空間，用它來存儲對應實參變量的地址，以便由系統自動引用實參變量。對于一個算法，其時間復雜度和空間復雜度往往是相互影響的。當追求一個較好的時間復雜度時，可能會使空間復雜度的性能變差，即可能導致占用較多的存儲空間；反之，當=i自求一個較好的空間復雜度時，可能會使時間復雜度的性能變差，即可能導致占用較長的運行時間。另外，算法的所有性能之間都存在著或多或少的相互影響。因此，當設計一個算法(特別是大型算法)時，要綜合考慮算法的各項性能，算法的使用頻率，算法處理的數據量的大小，算法描述語言的特性，算法運行的機器系統環境等各方面因素，才能夠設計出比較好的算法。空間復雜度是程序運行所以需要的額外消耗存儲空間,也用o()來表示比如插入排序的時間復雜度是o(n ²),空間復雜度是o(1)而一般的遞歸算法就要有o(n)的空間復雜度了,因為每次遞歸都要存儲返回信息一個算法的優劣主要從算法的執行時間和所需要占用的存儲空間兩個方面衡量，算法執行時間的度量不是采用算法執行的絕對時間來計算的，因為一個算法在不同的機器上執行所花的時間不一樣，在不同時刻也會由于計算機資源占用情況的不同，使得算法在同一臺計算機上執行的時間也不一樣，所以對于算法的時間復雜性，采用算法執行過程中其基本操作的執行次數，稱為計算量來度量。算法中基本操作的執行次數一般是與問題規模有關的，對于結點個數為n的數據處理問題，用T(n)表示算法基本操作的執行次數.在評價算法的時間復雜性時，不考慮兩算法執行次數之間的細小區別，而只關心算法的本質差別:為此，引入一個所謂的O() 記號，則T1(n)=2n=O(n),T2(n)=n+1=O(n)。一個函數f(n)是O(g(n))的，則一定存在正常數c和m，使對所有的n>m，都滿足f(n)<c*g(n)。

轉載于:https://www.cnblogs.com/yinfj/p/7126643.html

總結

以上是生活随笔為你收集整理的算法的性能评价------空间复杂度和时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。