算法分析
- 复杂性上界和平均复杂度的渐近分析；
- 最佳、最差和平均情况下的复杂度差异；
- 大O、Ω和 θ 符号
1 时间复杂度
1.1 步骤
1）分析某个语句的执行次数（频度） 2）分析某个程序段执行的时间复杂度（用大O表示，要求写出推导过程）
1.2 例子
- 例1
for (int i = 1; i <= n; i++)
for (int j = 1; j<=n; j++)
{ c[i][j] = 0.0;
for ( int k = 1; k <= n; k++)
c[i][j] = c[i][j]+a[i][k]*b[k][j];
}
次数为：n*n*n
- 例2
x = 0; y = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
for (int k = 1; k <= j; k++)
x = x+y;
次数为：n*(n+1)*(n+2)/6
- 例3
int x = 91; int y = 100;
while(y>0)
{ if(x>100) { x -= 10; y--; }
else x++;
}
次数为： 1100次
