这个了解吗;
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,
若有某个辅助函数f(n),使得T(n)/f(n)的极限值(当n趋近于无穷大时)为不等于零的常数,则称f(n)是T(n)的同数量级函数。
记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
随着模块n的增大,算法执行的时间的增长率和 f(n) 的增长率成正比,所以 f(n) 越小,算法的时间复杂度越低,算法的效率越高。
在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,
例:算法:
for(i=1; i<=n; ++i)
{
for(j=1; j<=n; ++j)
{
c[i][j] = 0;//该步骤属于基本操作执行次数:n的平方次
for(k=1; k<=n; ++k)
c[i][j] += a[i][k] * b[k][j];//该步骤属于基本操作执行次数:n的三次方次
}
}
则有
,根据上面括号里的同数量级,我们可以确定 n的三次方 为T(n)的同数量级
则有
,然后根据 T(n)/f(n) 求极限可得到常数c
则该算法的时间复杂度:T(n) = O(n^3) ;n^3即是n的3次方。
给的题有2个循环;要求哪个,还是总的;