【数据结构】时间复杂度的计算  配套例子详解

一、什么是算法：

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

算法的特征：

一个算法应该具有以下五个重要的特征：

有穷性（Finiteness）

算法的有穷性是指算法必须能在执行有限个步骤之后终止；

确切性(Definiteness)

算法的每一步骤必须有确切的定义；

输入项(Input)

一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

输出项(Output)

一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

可行性(Effectiveness)

算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

二、算法效率的度量：

虽然计算机能快速的完成运算处理，但实际上， 对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。所以，一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法的效率主要由以下两个复杂度来评估： 
时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的使用程度。 
空间复杂度：评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。

三、时间复杂度：

算法的时间复杂度是指执行算法所需要的计算工作量。是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。

T(n)=Ο(f(n))

不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

大O表示法O(f(n)中的f(n)的值可以为1、n、logn、n²等，因此我们可以将O(1)、O(n)、O(logn)、O(n²)分别可以称为常数阶、线性阶、对数阶和平方阶。

常数阶 

// 常数阶

int result = 100; //运行程序只执行一次  

result ++ ;  //执行一次

System.out.println ("Hello!"+result); //执行一次 

上面算法的运行的次数的函数为f(n)=3，根据推导大O阶的规则1，每次运行程序每条语句执行一次，所以这个算法的时间复杂度仍旧是O(1)，我们可以称之为常数阶。

线性阶 

//线性阶

for(int i=0;i<n;i++){

   System.out.println(result[i]);  //执行一次

}

线性阶主要要分析循环结构的运行情况。上面算法循环体中的代码执行了n次，因此时间复杂度为O(n)，实际上，在for循环里面的所有时间复杂度为O(1)的语句总的时间复杂度都是O(n)。

对数阶 

// 对数阶

int result=1;

while(result<n){

    result=result*2; //时间复杂度为O(1)

}

可以看出上面的代码，随着result每次乘以2后，都会越来越接近n，当result大于等于n时就会退出循环。如果循环的次数为T，所以2^T=n于是T=log₂n，因此得出这个算法的时间复杂度为O(logn)。

平方阶 

// 平方阶

for(int i=0;i<n;i++){  
 
   for(int j=0;j<n;i++){

       System.out.println(result[i][j]);  //执行一次

   }

}

这是一个循环嵌套的语句，很明显内层循环的时间复杂度在讲到线性阶时就已经得知是O(n)，又经过了外层循环n次，那么这段算法的时间复杂度则为O(n²)。 

多个复杂度组合：顺序结构

// 多个复杂度组合

for(int i=0;i<n;i++){  
 
   for(int j=0;j<n;i++){

       System.out.println(result[i][j]);  //执行一次

   }

}

for(int i=0;i<n;i++){  

   System.out.println(result[i]);  //执行一次

}

对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。所以对于以上的代码，时间复杂度为O(n²)。 

多个复杂度组合：选择结构

// 多个复杂度组合
if(flag){

   for(int i=0;i<n;i++){  
 
       for(int j=0;j<n;i++){

          System.out.println(result[i][j]);  //执行一次

       }

    }

}else{

    for(int i=0;i<n;i++){  

       System.out.println(result[i]);  //执行一次

    }

}

对于条件判断语句，总的时间复杂度等于其中时间复杂度最大的路径的时间复杂度。所以对于以上的代码，时间复杂度为O(n²)。 

四、例子评注说明：

 

//题目一
void fun(int n){
    int i,j,x=0;
    for(i=1;i<n;i++){
       for(j=n;j>=i+1;j--){
           x++;
       }
    }
}

【分析】基本运算是语句 x++，假设执行次数为T(n)，则有 ，所以时间复杂度为O()。

//题目二
void fun(int n){
    int i=0;
    while(i*i*i<=n){
        i++;
    }
}

【分析】基本运算是语句 x++，假设执行次数为T(n)，则有 ，即，所以时间复杂度为。

//题目三
int m=0,i,j;
for(i=1;i<=n;i++){
    for(j=1;j<=2*i;j++){
        m++;
    }
}

【分析】基本运算是语句 m++，假设执行次数为T(n)，则有 ，所以时间复杂度为O()。

//题目四
void fun(int n){
    int i,k;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            k=1;
            while(k<=n){
                k = 5*k;
            }
        }
    }
}

【分析】基本运算是语句 k = 5*k;，假设执行时间为T(n)，对于j每循环一次，该语句的执行次数为m，有，即则有 。

掌握一定的解题技巧，所有同类型的就可以迎刃而解了。