数据结构系列之复杂度分析

1 时间复杂度

        求解算法的时间复杂度的具体步骤是&＃xff1a;

　　⑴ 找出算法中的基本语句&＃xff1b;

　　算法中执行次数最多的那条语句就是基本语句&＃xff0c;通常是最内层循环的循环体。

　　⑵ 计算基本语句的执行次数的数量级&＃xff1b;

　　只需计算基本语句执行次数的数量级&＃xff0c;这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可&＃xff0c;可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分         析&＃xff0c;并且使注意力集中在最重要的一点上&＃xff1a;增长率。

　　⑶ 用大Ο记号表示算法的时间性能。

　　将基本语句执行次数的数量级放入大Ο记号中。

　　如果算法中包含嵌套的循环&＃xff0c;则基本语句通常是最内层的循环体&＃xff0c;如果算法中包含并列的循环&＃xff0c;则将并列循环的时间复杂度相加。例如&＃xff1a;

       for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
　　   x&＃43;&＃43;;

       for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
           for(j&＃61;1;j<&＃61;n;j&＃43;&＃43;)
　　       x&＃43;&＃43;;

　　第一个for循环的时间复杂度为Ο(n)&＃xff0c;第二个for循环的时间复杂度为Ο(n2)&＃xff0c;则整个算法的时间复杂度为Ο(n&＃43;n2)&＃61;Ο(n2)。

　　常见的算法时间复杂度由小到大依次为&＃xff1a;

　　Ο(1)&＃xff1c;Ο(log2n)&＃xff1c;Ο(n)&＃xff1c;Ο(nlog2n)&＃xff1c;Ο(n2)&＃xff1c;Ο(n3)&＃xff1c;…&＃xff1c;Ο(2n)&＃xff1c;Ο(n!)

       Ο(1)表示基本语句的执行次数是一个常数&＃xff0c;一般来说&＃xff0c;只要算法中不存在循环语句&＃xff0c;其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时       间&＃xff0c;而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法&＃xff0c;把这类问题称为P类问题&＃xff0c;而把后者称为NP问题。

2 空间复杂度

       空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间&＃xff0c;包括存储算法本身所占用的存储空    间&＃xff0c;算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

      一般情况下&＃xff0c;一个程序在机器上执行时&＃xff0c;除了需要存储程序本身的指令、常数、变量和输入数据外&＃xff0c;还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题        本身&＃xff0c;和算法无关&＃xff0c;这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数&＃xff0c;则称此算法为原地工作&＃xff0c;空间复         杂度为O(1)。

     关于O(1)的问题&＃xff0c; O(1)是说数据规模和临时变量数目无关&＃xff0c;并不是说仅仅定义一个临时变量。举例&＃xff1a;无论数据规模多大&＃xff0c;我都定义100个变量&＃xff0c;这就叫做数据规模和临时变量    数目无关。就是说空间复杂度是O(1)。