牢记一句话:
-
将算法中的
基本操作
的执行次数
作为算法时间复杂度的度量 !在分析过程中总能找到一个 n ,称之为问题的规模。
步骤:
step 1 : 找到基本操作(多数情况下为最深层循环内语句的操作),确定规模 n .
step 2 : 计算出 f(n) : 由规模 n , 执行次数 k 的关系确定k = f(n)
step 3 : O(f(n)) : f(n)中增长最快的项
例
分析一下代码时间复杂度
EX 1:
void fun(int n)
{
int i, j, x=0;
for(i=1; i< n; ++i)
{
for(j=i+1; j<=n; ++j)
{
++x;
}
}
return;
}
EX 2:
void fun(int n)
{
int i = 0;
int s = 0;
while(s < n)
{
++i;
s = s+i;
}
return;
}