时间复杂度如何计算_for(i=1,i<=n,i*=2)for(j=1,j<=n,j++)的时间复杂度)

算法时间复杂度：

时间复杂度描述的是方法执行的渐进时间复杂度（随着数据的增加的一种时间变化趋势）

用T(n)=O(f(n)) 表示。其中 f（n）表示当数据量为n的时候这个方法中的代码的执行次数总和

 

代码1

int i = 1; 
int j = 2; 
++i;
j++; 
int m = i + j;

如上面代码所示

代码没有循环 上面的代码执行次数与数据量无关，永远都是5则f（n）=5

则这段代码的时间复杂度T（n）=O（f（n））=O（5）可以简化为O（1）

为什么可以这么去简化呢，因为大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的

 

代码2

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

如上面代码所示

第1行代码执行次数为n[循环判断n次] 第3行代码执行次数为n[因为在for循环中]，同理第4行代码执行次数也为n

则这段代码的执行总次数f（n）=n+n+n=3n

则时间复杂度T（n）=O（f（n））=O（3n） 可以简化为O（n）

因为当数据量无穷大的时候，常量就没有意义了，倍数3意义不大。因此直接简化为T(n) = O(n) 就可以了

 

代码3

int i = 1; 
while(i<n) 
{
  i = i * 2; 
}

如上面代码所示

第1行代码执行次数为1

第2行代码与第4行执行的次数都为 i:当2的i次方大于等于n时循环结束，则2^i>=n，则执行次数 i=log2^n

则这段代码的执行次数f（n）=1+log2^n+log2^n=2log2^n+1

则T（n）=O（f（n））=O（2log2^n+1）=O（log2^n）=O（logn）

因为当数据量无穷大的时候，常量1就没有意义了，倍数2也意义不大。因此直接简化为T(n) = O(log2^n) =O（logn）就可以了 底数2可以直接省略了，为什么可以省略底数如下所示：

正在上传…重新上传取消

 

 

 

 

假设有底数为2和3的两个对数函数，如上图。当X取N（数据规模）时，求所对应的时间复杂度得比值，即对数函数对应的y值，用来衡量对数底数对时间复杂度的影响。

 

比值为log2 N / log3 N，运用换底公式后得：(lnN/ln2) / (lnN/ln3) = ln3 / ln2，ln为自然对数，显然这是个常数，与变量N无关，可以直接省略。

 

时间复杂度描述的是随着数据增加的时间变化趋势。如上图，2跟3不同底数对应的时间复杂度的倍数关系为常数，不会随着底数的不同而不同，因此可以将不同底数的对数函数所代表的时间复杂度，当作是同一类复杂度处理，即抽象成一类问题。

 

代码4

for(m=1; m<n; m++) 
{ 
  i = 1; 
  while(i<n) {
    i = i * 2; 
  } 
}

如上代码所示

第1行执行次数为n

第3行为n

第4行为n log2^n（循环里面套循环）

低5行为n log2^n（循环里面套循环）

则总的执行次数为n（ 2nlog2^n+1）=O（nlog2^n）=O(nlogn)