【自考】算法——时间复杂度汇总

整理了自考《数据结构》中的所有时间复杂度，制作了如下几张表，便于对比和记忆，请笑纳。

       常见时间复杂度排序：

        O(1)<O(log₂n)<O(n)<O(nlog₂n)<O(n²)<O(n³)<O(Cⁿ)（指数阶）

       时间复杂度，填空和选择会有不少于8分的题目。除了上述书中列出的，还有给一小段程序，让自己计算的。

       时间复杂度的计算，从出题的规律来看，莫不是O(√n)、O(n)、O(log₂n)、O(n²)、O(n³)这几种之一。

   除了按照常规方法计算基本运算的次数之外，考试中时间复杂度的题也很有规律性。

   1、看有几层循环，一层循环，是O(√n)或者O(log₂n)或者O（n）；两层循环，是O(n²)；三层循环，是O(n³)。（一般规律如此，具体问题具体分析）

   2、一层循环中到底是哪一个，对照下面代码，很快就能总结出来。

   判断一下这几段程序的时间复杂度是多少？

1、

1. for(i=1;i<=n;i++)
2. {
3.     m++;
4. for(j=1;j<=n;j++)
5.         k*=m;
6. }

2、

1. for (i=1; i<=n; i++)
2. for (j=1; j<=n; j++)
3. for (k=1;k<=n;k++)
4.             x++；

3、

1.    i=0；s=0；
2. while(s<n)
3.    { i++；
4.       s=s+i；
5.     }

4、

1.    i=0；s=0；
2. while（i<n）
3.    { i++；
4.      s=s+i；
5.    }

5、

1.    i=1； 
2. while（i<n）  
3.        i=i*2；

6、下边这是一个变种，看看它的时间复杂度是多少？

1. for ( int i=0; i<m; i++)
2. for ( int j=0; j<n; j++)
3.         a［i］［j］=i*j;

————————————————

答案：1、O(n²) 2、O(n³) 3、O(√n) 4、O(n) 5、O(log₂n)6、O(mn)

你的答案对吗？