【算法与数据结构】关于代码运行时间复杂度的计算方法

(转载请注明出处:http://blog.csdn.net/buptgshengod

1.背景知识

       大O标记就不用我说了吧。O(n)这种时间复杂度的意义自己google吧。这里简单讲下从代码推算。

2.具体案例

 (1)案例一

  
int a=0;                      //第一行
for(int i=0;i<=N;i++)//第二行
{
  a+=i*i*i;                  //第三行
}
我们来看下。
第一行,声明变量并赋值用一个时间单元;
第二行,首先给i赋值,一个时间单元。i<=N是N+1个时间单元。i++是N个时间单元。第二行总共2N+2个时间单元。
第三行,一个加法,一个赋值,两个乘法,一共四个时间单元。执行N次,一共4N个时间单元。

所以这段代码一共6N+3个时间单元。时间复杂度为O(N);

(2)案例二

   一个for循环
for(int i=0;i<=N;i++)
时间复杂度O(n)

 
  嵌套for循环
for(i=0;i<n;i++)
{
   for(j=0;j<n;j++)
 {}
}
时间复杂度O(n²)


 三层嵌套语句
for(m=0;m<n;m++)
{
    int a=0;
    for(i=0;i<n;i++)
   {
       for(j=0;j<n;j++)
      {}
    }
}
时间复杂度为O(n³)。

if/else语句
时间复杂度,是if和else中最长的那个。


简单的递归函数如
public static int test(int n)
{
     if(n<=1)
      {
         return 1;
       }
     else
       {
        return n*test(n-1);
       }
}
相当与一个for的循环,时间复杂的是O(n)


上一篇:C#中通过Selenium定位标签的问题


下一篇:走进JavaWeb技术世界12:从手动编译打包到项目构建工具Maven