时间复杂度的简单例题

时间复杂度

1.概念：时间复杂度是指在算法中基本操作重复执行的次数，可表达为O(1)，O(n)等。

2.例题

（1）for(i=1;i<=n;i++)

        K++;

for(j=1,j<=n;j++)

m+=k;

解析：这两个循环是互不联系的循环，上面一个语句循环完之后再循环下面一个语句，且上面语句循环n次，下面也循环了n次，所以总共循环了2n次，则时间复杂度为O(n)。

(2)  void fun()

     {

       int i=1,k=0,n=10;

       while(i<=n-1)

       {

         k+=10*i;

         ++I;

}

}

解析：for(i=1;i<=n-1;++i), 所以时间复杂度就等于O(log2n),故时间复杂度为O(n)。

(3) void func(int n)

   {

int i=0,s=0;

While (s<=n)

{

  i++;

s=s+i

}

}

解析：已知被执行次数为T(n)次,i每循环一次就递增1，直到循环到T(n)次为止，s=1+2+3+…+T(n)，s=T(n)*T((n)-1)/2，所以T(n)= O(√n)，则时间复杂度为O(√n)。

(4)  void fun()

{

 i=1;

 while(i<=n)

   i=i*2;

}

解析：本题中基本运算语句是i*2，频度为T(n)，所以T(n)<=log2n，则时间复杂度为O(log2n)。

(5)  int m=0,i,j;

For(i=1;i<=n;i++)

  For(j=1;j<=2*I;j++)

      m++;

解析：i=1，执行2次，i=2执行4次，i=3执行6次….i=n执行2n次，所以T(n)=n*(2+2*n)/2=n*(n+1)，则时间复杂度为O(n*n)。

最后

以上就是机智蜗牛为你收集整理的时间复杂度的简单例题的全部内容，希望文章能够帮你解决时间复杂度的简单例题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。