程序在计算机上运行所需时间的影响因素

算法本身选用的策略

问题的规模

规模越大，消耗时间越多

书写程序的语言

语言越高级，消耗时间越多

编译产生的机器代码质量

机器执行指令的速度

求4*4矩阵元素和，T(4)=O(f(4))
f=n*n;

sum(int num[4][4])
{ int i,j,r=0; 
for(i=0;i<4;i++)
for(j=0;j<4;j++)
r+=num[i][j]; /*原操作*/
return r; 
}

最好情况：
T（4）=O（0）
最坏情况：
T（4）=O（n*n）

ispass(int num[4][4])
{ int i,j; 
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(num[i][j]!=i*4+j+1)
return 0;
return 1; 
}

语句

频度

时间复杂度

{++x;s=0;}

1

O(1)

for(i=1;i<=n;++i)
{++x;s+=x;}

n

O(n)

for(j=1;j<=n;++j)
for(k=1;k<=n;++k)
{++x;s+=x;}

n*n

O(n*n)

O(log n)

基本操作的执行次数不确定时的时间复杂度

平均时间复杂度

依基本操作执行次数概率计算平均

最坏情况下时间复杂度

在最坏情况下基本操作执行次数