演算法的時間復雜度舉例說明

① 演算法復雜度的時間復雜度

（1）時間頻度
一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。演算法的時間復雜度是指執行演算法所需要的計算工作量。
（2）時間復雜度
在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間復雜度概念。
一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T(n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。
在各種不同演算法中，若演算法中語句執行次數為一個常數，則時間復雜度為O(1),另外，在時間頻度不相同時，時間復雜度有可能相同，如T(n)=n^2+3n+4與T(n)=4n^2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n^2)。
按數量級遞增排列，常見的時間復雜度有：
常數階O(1),對數階O(log2n)(以2為底n的對數，下同),線性階O(n),
線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，
k次方階O(n^k),指數階O(2^n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。
演算法的時間性能分析
（1）演算法耗費的時間和語句頻度
一個演算法所耗費的時間=演算法中每條語句的執行時間之和
每條語句的執行時間=語句的執行次數(即頻度(Frequency Count))×語句執行一次所需時間
演算法轉換為程序後，每條語句執行一次所需的時間取決於機器的指令性能、速度以及編譯所產生的代碼質量等難以確定的因素。
若要獨立於機器的軟、硬體系統來分析演算法的時間耗費，則設每條語句執行一次所需的時間均是單位時間，一個演算法的時間耗費就是該演算法中所有語句的頻度之和。
求兩個n階方陣的乘積 C=A×B,其演算法如下:
# define n 100 // n 可根據需要定義,這里假定為100
void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n])
{ //右邊列為各語句的頻度
int i ,j ,k;
(1) for(i=0; i<n;i++) n+1
(2) for (j=0;j<n;j++) { n(n+1)
(3) C[i][j]=0; n2
(4) for (k=0; k<n; k++) n2(n+1)
(5) C[i][j]=C[i][j]+A[i][k]*B[k][j];n3
}
}
該演算法中所有語句的頻度之和(即演算法的時間耗費)為：
T(n)=2n3+3n2+2n+1 (1.1)
分析：
語句(1)的循環控制變數i要增加到n，測試到i=n成立才會終止。故它的頻度是n+1。但是它的循環體卻只能執行n次。語句(2)作為語句(1)循環體內的語句應該執行n次，但語句(2)本身要執行n+1次，所以語句(2)的頻度是n(n+1)。同理可得語句(3)，(4)和(5)的頻度分別是n2，n2(n+1)和n3。
演算法MatrixMultiply的時間耗費T(n)是矩陣階數n的函數。
（2）問題規模和演算法的時間復雜度
演算法求解問題的輸入量稱為問題的規模(Size),一般用一個整數表示。
矩陣乘積問題的規模是矩陣的階數。
一個圖論問題的規模則是圖中的頂點數或邊數。
一個演算法的時間復雜度(Time Complexity, 也稱時間復雜性)T(n)是該演算法的時間耗費，是該演算法所求解問題規模n的函數。當問題的規模n趨向無窮大時，時間復雜度T(n)的數量級(階)稱為演算法的漸進時間復雜度。
演算法MatrixMultiply的時間復雜度T(n)如(1.1)式所示，當n趨向無窮大時，顯然有T(n)~O(n^3);
這表明，當n充分大時，T(n)和n^3之比是一個不等於零的常數。即T(n)和n^3是同階的，或者說T(n)和n^3的數量級相同。記作T(n)=O(n^3)是演算法MatrixMultiply的漸近時間復雜度。
（3）漸進時間復雜度評價演算法時間性能
主要用演算法時間復雜度的數量級(即演算法的漸近時間復雜度)評價一個演算法的時間性能。
演算法MatrixMultiply的時間復雜度一般為T(n)=O(n^3)，f(n)=n^3是該演算法中語句(5)的頻度。下面再舉例說明如何求演算法的時間復雜度。
交換i和j的內容。
Temp=i;
i=j;
j=temp;
以上三條單個語句的頻度均為1，該程序段的執行時間是一個與問題規模n無關的常數。演算法的時間復雜度為常數階，記作T(n)=O(1)。
注意：如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是一個較大的常數。此類演算法的時間復雜度是O(1)。
變數計數之一：
(1) x=0;y=0;
(2) for(k-1;k<=n;k++)
(3) x++;
(4) for(i=1;i<=n;i++)
(5) for(j=1;j<=n;j++)
(6) y++;
一般情況下，對步進循環語句只需考慮循環體中語句的執行次數，忽略該語句中步長加1、終值判別、控制轉移等成分。因此，以上程序段中頻度最大的語句是(6)，其頻度為f(n)=n^2，所以該程序段的時間復雜度為T(n)=O(n^2)。
當有若干個循環語句時，演算法的時間復雜度是由嵌套層數最多的循環語句中最內層語句的頻度f(n)決定的。
變數計數之二：
(1) x=1;
(2) for(i=1;i<=n;i++)
(3) for(j=1;j<=i;j++)
(4) for(k=1;k<=j;k++)
(5) x++;
該程序段中頻度最大的語句是(5)，內循環的執行次數雖然與問題規模n沒有直接關系，但是卻與外層循環的變數取值有關，而最外層循環的次數直接與n有關，因此可以從內層循環向外層分析語句(5)的執行次數：
則該程序段的時間復雜度為T(n)=O(n^3/6+低次項)=O(n^3)。
（4）演算法的時間復雜度不僅僅依賴於問題的規模，還與輸入實例的初始狀態有關。
在數值A[0..n-1]中查找給定值K的演算法大致如下：
(1)i=n-1;
(2)while(i>=0&&(A[i]!=k))
(3) i--;
(4)return i;
此演算法中的語句(3)的頻度不僅與問題規模n有關，還與輸入實例中A的各元素取值及K的取值有關:
①若A中沒有與K相等的元素，則語句(3)的頻度f(n)=n；
②若A的最後一個元素等於K,則語句(3)的頻度f(n)是常數0。

② 演算法的時間復雜度怎樣計算舉例子詳細說明，謝謝。

循環次數搞清，時間復雜度自然就出來了。
for( i = 1; i <= n; ++ i )
for( j = 1; j <= i; ++ j )
外循環n次，對應每次外循環，內循環次數為1.2.3.4....n次,循環總次數 : n( n + 1 )/2
因此復雜度為O(n2)

③ 什麼是演算法的時間復雜度 畫圖說明

比如：
一個for循環
for（i=0; i<n;i++）
{}
這個演算法的復雜性就是n，或者說是線性的.
再比如
for（i=0; i<n;i++）
{
for（j=0; j<n;j++）{
}

}
這個演算法的復雜性就是n的平方
希望我說的還算詳細

④ 1.3 請說明下列演算法的時間復雜度.

這個首先要明確一點，只用到比較的排序演算法最低時間復雜度是O(nlogn)，而像桶排這樣的只需要O(R)(R為桶的大小)。
為了證明只用到比較的排序演算法最低時間復雜度是O(nlogn)，首先要引入決策樹。
首先決策樹是一顆二叉樹，每個節點表示元素之間一組可能的排序，它予以京進行的比較相一致，比較的結果是樹的邊。
先來說明一些二叉樹的性質，令T是深度為d的二叉樹，則T最多有2^片樹葉。
具有L片樹葉的二叉樹的深度至少是logL。
所以，對n個元素排序的決策樹必然有n!片樹葉（因為n個數有n!種不同的大小關系），所以決策樹的深度至少是log(n!)，即至少需要log(n!)次比較。

⑤ 請問遞歸演算法的時間復雜度如何計算呢

遞歸演算法的時間復雜度在演算法中，當一個演算法中包含遞歸調用時，其時間復雜度的分析會轉化為一個遞歸方程求解，常用以下四種方法：

1.代入法(Substitution Method)

代入法的基本步驟是先推測遞歸方程的顯式解，然後用數學歸納法來驗證該解是否合理。

2.遞歸程序設計是程序設計中常用的一種方法，它可以解決所有有遞歸屬性的問題，並且是行之有效的.

3.但對於遞歸程序運行的效率比較低，無論是時間還是空間都比非遞歸程序更費，若在程序中消除遞歸調用，則其運行時間可大為節省.

⑥ 什麼是演算法的時間復雜度

是說明一個程序根據其數據n的規模大小 所使用的大致時間和空間
說白了 就是表示 如果隨著n的增長 時間或空間會以什麼樣的方式進行增長

例
for(int i = 0; i < n;++i)
;
這個循環執行n次 所以時間復雜度是O(n)

for(int i = 0; i< n;++i)
{
for(int j = 0; j< n;++j)
;
}
這嵌套的兩個循環 而且都執行n次
那麼它的時間復雜度就是 O(n^2)

時間復雜度只能大概的表示所用的時間
而一些基本步驟 所運行的時間不同 我們無法計算 所以省略
如

for(int i = 0;i < n;++i)
a = b;
和
for(int i = 0;i < n;++i)
;
這個運行的時間當然是第二個快 但是他們的時間復雜度都是 O(n)
判斷時間復雜度看循環

⑦ 如何計算時間復雜度

1、先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出T（n）的同數量級（它的同數量級有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出後，f（n）=該數量級，若T(n)/f(n)求極限可得到一常數c，則時間復雜度T（n）=O（f（n））。

2、舉例

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的三次方）

),線性階O(n),線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，

k次方階O(n^k),指數階O(2^n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。

關於對其的理解

《數據結構（C語言版）》 ------嚴蔚敏 吳偉民編著 第15頁有句話「整個演算法的執行時間與基本操作重復執行的次數成正比。」

基本操作重復執行的次數是問題規模n的某個函數f(n)，於是演算法的時間量度可以記為：T(n) = O(f(n))

如果按照這么推斷，T(n)應該表示的是演算法的時間量度，也就是演算法執行的時間。

而該頁對「語句頻度」也有定義：指的是該語句重復執行的次數。

如果是基本操作所在語句重復執行的次數，那麼就該是f(n)。

上邊的n都表示的問題規模。

⑧ 演算法時間復雜度的計算例題

第一題：
int i=1,k=100這條語句演算法步數是2步,執行頻率是1；
循環中, k=k+1;這條語句每次演算法步數是1；執行頻率是n/2-1; i+=2這條語句每次演算法步數是1；執行頻率是n/2-1;
所以演算法復雜度為1*（n/2-1）+1*（n/2-1）+2=n=o(n);

⑨ 請說明下列演算法的時間復雜度。

（1）O(n)。外層for循環O(n)；內層for循環O(1)，因為是常數個循環；x+=2為O(1)。則總的時間復雜度為O(n)。
（2）O(n^2)。外層for循環O(n)；內層for循環O(n)；兩者都是線性時間復雜度。x++為O(1)。則總的時間復雜度為O(n^2)。

⑩ 演算法時間復雜度的分析

不是呢。
關鍵要看n的大小和常量系數。
比如： O(N)的演算法實際是20n， 而O(n^2)的演算法實際是n^2
當輸入數據規模n=10的時候，前者 是20*10 = 200 > 10^2 = 100.