示例代码展示

1.for(i=1;i<=n;i++){										//n+1次
2. 	for(j=1;j<=n;j++){									//n(n+1)次
3. 		c[i][j]=0;											//n*n次
4.		for(k=0;k<n;k++)								//n*n*(n+1)次
5.			c[i][[j]=c[i][[j]+a[i][j]*b[k][j];			//n*n*n次
6.	}
7.}

示例代码为两个n × n矩阵相乘的算法

• 我们把算法所耗费的时间定义为该算法每条语句的频度之和：
  T(n)=2n³ +3n² 2n+1

算法的时间复杂度例题

 1. i=1;
 2. while(i<=n)
 3. 	i=i*2;

1. 若循环执行一次：i=1*2=2，
2. 若循环执行一次：i=2*2=2²,
3. 若循环执行一次：i=2*2=2³,
4. 若循环执行X次：i=2^x
   设语句 i+i*2 执行次数为x次，
   由循环条件i<=n，所以2^x <=n，所以 x<=log₂ n

2^f(n) <=n，即f(n)<=log² n，取最大值，f(n) = log² n，
所以该程序段的时间复杂度T(n)=O(log₂ n)。

实例代码

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
       for (int k = j + 1; k < n; k++) {
            count++;
       }
    }
}

以上代码中，求count++语句的执行次数。

其实这段代码中求count++语句的执行次数等价于：从n个整数中取出三个整数的组合总共有多少种（不考虑顺序，1,2,3 2,3,1 等算一种）。

求解过程

$n>2时：$

      $当i=0时，j=1\sim (n-1)，count的执行次数为((n-1)-1)+(n-3)+(n-4)+\cdots +2+1$

      $当i=1时，j=2\sim (n-1)，count的执行次数为((n-1)-2)+(n-4)+(n-5)\cdots +2+1$

      $当i=2时，j=3\sim (n-1)，count的执行次数为((n-1)-3)+(n-5)+\cdots +2+1$

                                          $⋮$

      $当i=n-3时，j=(n-2)\sim (n-1)，count的执行次数为1$

      $当i=n-2时，j=(n-1)，count的执行次数为0$

可以看出，每次i产生变化时，count++语句的执行次数都是一个等差数列，可由等差数列求和公式：
$$S_n=\frac{n(a_1+a_n)}{2}=1+2+\cdots +n=\frac{n(1+n)}{2}=\frac{n^2+n}{2}$$
count++总执行次数$S_n:$
$$\begin{gathered} S_n=\frac{(n-2{)}^2+(n-2)}{2}+\frac{(n-3{)}^2+(n-3)}{2}+\cdots +\frac{2^2+2}{2}+\frac{1^2+1}{2} \\ =\frac{((n-2{)}^2+(n-3{)}^2+\cdots +2^2+1^2)+((n-2)+(n-3)+\cdots +2+1)}{2} \end{gathered}$$
再由公式：
$$1^2+2^2+\cdots +n^2=\frac{n(n+1)(2n+1)}{6}$$
得：
$$\begin{gathered} S_n=\frac{\frac{(n-2)(n-2+1)(2(n-2)+1)}{6}+\frac{(n-2{)}^2+(n-2)}{2}}{2} \\ =\frac{n(n-1)(n-2)}{6} \end{gathered}$$
$0<n<2时：$

count++的执行次数为0，$n>2$的公式仍适用于$0<n<2$的情况。

即：

count++语句的执行次数为$\frac{n(n-1)(n-2)}{6}$

参考文章

一个小问题：计算3层循环的执行次数