複雜度

一、引言

    一個算法是由控制結構（順序、分支和循環3種）和原操作（指固有資料類型的操作）構成的，則算法時間取決于兩者的綜合效果。為了便于比較同一問題的不同算法，通常的做法是：從算法中選取一種對于所研究的問題來說的基本操作的原操作，以該基本操作重複執行的次數作為算法的時間量度。

    例如：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

<code>for</code><code>(i=1;i&lt;=n;i++)</code>

<code>{</code>

<code>   </code><code>for</code><code>（j=1;j&lt;=n;j++）</code>

<code>   </code><code>{</code>

<code>c[i][j] = 0;</code>

<code>for</code><code>(k=1;k&lt;=n;k++)</code>

<code>c[i][j] += a[i][k]*b[k][j];</code>

<code>}</code>

<code>   </code><code>}</code>

　　

在兩個n*n矩陣相乘的算法中，乘法運算是矩陣相乘問題的基本操作。整個算法的執行時間與該基本操作重複執行的次數n^3成正比，記做

        t(n) = o(n^3);

一般情況下，算法中基本操作重複執行的次數是問題規模n的某個函數f(n)，算法的時間量度記作

        t(n) = o(f(n)); 

它表示随着問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間複雜度，簡稱時間複雜度。

    大多數情況下，問題基本操作的原操作是最深層循環内的語句中的原操作，它的執行次數和包含它的語句的頻度相同。語句的頻度指的是該語句重複執行的次數，例如

<code>1、{a++;s=0;}</code>

<code>2、</code><code>for</code><code>(i=1;i&lt;=n;i++){a++;s+=x;}</code>

<code>3、</code><code>for</code><code>(j=1;j&lt;=n;j++)</code>

<code>    </code><code>{</code>

<code>    </code><code>a++;s+=x;</code>

<code>    </code><code>}</code>

這三個程式的時間複雜度分别為o(1)、o(n)和o(n^2),分别成為常量階、線性階、平方階。