复杂度

一、引言

    一个算法是由控制结构（顺序、分支和循环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),分别成为常量阶、线性阶、平方阶。