標籤:數據結構時間複雜度空間複雜度

同一問題可用不同演算法解決,而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。

1演算法複雜度

演算法複雜度分為時間複雜度和空間複雜度。其作用: 時間複雜度是指執行演算法所需要的計算工作量;而空間複雜度是指執行這個演算法所需要的內存空間。(演算法的複雜性體現在運行該演算法時的計算機所需資源的多少上,計算機資源最重要的是時間和空間(即寄存器)資源,因此複雜度分為時間和空間複雜度。)

2時間複雜度

計算方法
1. 一般情況下,演算法的基本操作重複執行的次數是模塊n的某一個函數f(n),因此,演算法的時間複雜度記做:T(n)=O(f(n))
分析:隨著模塊n的增大,演算法執行的時間的增長率和f(n)的增長率成正比,所以f(n)越小,演算法的時間複雜度越低,演算法的效率越高。
2. 在計算時間複雜度的時候,先找出演算法的基本操作,然後根據相應的各語句確定它的執行次數,再找出T(n)的同數量級(它的同數量級有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=該數量級,若T(n)/f(n)求極限可得到一常數c,則時間複雜度T(n)=O(f(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^3) 註:n^3即是n的3次方。
3.在pascal中比較容易理解,容易計算的方法是:看看有幾重for循環,只有一重則時間複雜度為O(n),二重則為O(n^2),依此類推,如果有二分則為O(logn),二分例如快速冪、二分查找,如果一個for循環套一個二分,那麼時間複雜度則為O(nlogn)。
關於對其的理解
《數據結構(C語言版)》------嚴蔚敏 吳偉民編著 第15頁有句話"整個演算法的執行時間與基本操作重複執行的次數成正比。"
基本操作重複執行的次數是問題規模n的某個函數f(n),於是演算法的時間量度可以記為:T(n) = O( f(n) )
如果按照這麼推斷,T(n)應該表示的是演算法的時間量度,也就是演算法執行的時間。
而該頁對「語句頻度」也有定義:指的是該語句重複執行的次數。
如果是基本操作所在語句重複執行的次數,那麼就該是f(n)。
上邊的n都表示的問題規模。

3空間複雜度

一個程序的空間複雜度是指運行完一個程序所需內存的大小。利用程序的空間複雜度,可以對程序的運行所需要的內存多少有個預先估計。一個程序執行時除了需要存儲空間和存儲本身所使用的指令、常數、變數和輸入數據外,還需要一些對數據進行操作的工作單元和存儲一些為現實計算所需信息的輔助空間。程序執行時所需存儲空間包括以下兩部分。
(1)固定部分。這部分空間的大小與輸入/輸出的數據的個數多少、數值無關。主要包括指令空間(即代碼空間)、數據空間(常量、簡單變數)等所佔的空間。這部分屬於靜態空間。
(2)可變空間,這部分空間的主要包括動態分配的空間,以及遞歸棧所需的空間等。這部分的空間大小與演算法有關。
一個演算法所需的存儲空間用f(n)表示。
S(n)=O(f(n))
其中n為問題的規模,S(n)表示空間複雜度。
上一篇[空間複雜度]    下一篇 [演算法效率]

相關評論

同義詞:暫無同義詞