首页 > 专题系列 > 算法分析 > 算法分析(1)-循环的时间复杂度
2014
03-12

算法分析(1)-循环的时间复杂度

在这篇文章中,我们用简单的循环程序进行分析讨论时间复杂度。

1) O(1)

一个函数调用或是一组语句都认为是O(1)的复杂度  (如果没有调用不包含循环,递归或其他非常量复杂度的函数)。

// set of non-recursive and non-loop statements

例如函数 swap()  是 O(1)的时间复杂度. 如果循环的次数是一个常量,则也认为是 O(1)

//这里C为常数    
   for (int i = 1; i <= n; i += c) {  
       //一些 O(1) 的语句
   }
   for (int i = n; i > 0; i -= c) {
       //一些 O(1) 的语句
   }

2) O(n)

如果在一个大小为n循环中,循环变量按照一个常量C递增或递减,这个循环的复杂度就为O(n).

 // c是常量   
   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

3) O(nc)

嵌套循环的时间复杂度等于行最内层语句执行的次数。例如,下面的示例循环具有为O(n 2)的时间复杂度

 for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some O(1) expressions
       }
   }

   for (int i = n; i > 0; i += c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
   }

例如选择排序插入排序具有为O(n 2)的时间复杂度。

4) O(Log n)

如果在一个大小为n循环中,循环变量按照一个常量C的进行倍数的递增或递减,这个循环的复杂度就为O(Log  n).

 for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
   }
   for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
   }

5) O(Log Log n)

如果在一个大小为n循环中,循环变量是指数级的递增或递减,这个循环的复杂度就为O(Log log n).

 // c为比1大的常量 
   for (int i = 2; i <=n; i = pow(i, c)) { 
       // some O(1) expressions
   }
   //这里的 fun 函数可以是sqrt 或 cuberoot 或任何其他恒定的根
   for (int i = n; i > 0; i = fun(i)) { 
       // some O(1) expressions
   }

如何计算连续循环的复杂性?

当有连续的循环,我们计算时间复杂度为时间各个循环的复杂总和。

   for (int i = 1; i <=m; i += c) {  
        // some O(1) expressions
   }
   for (int i = 1; i <=n; i += c) {
        // some O(1) expressions
   }
   上面的时间复杂度 O(m) + O(n) = O(m+n)
   如果 m == n 就是 O(2n),也可缩写为 O(n) 常量可以忽略不计

如果循环中有许多if …else 如何计算时间复杂度?

一般情况我们只考虑最快情况下的复杂度。例如考虑线性搜索函数,我们只考虑元素出现在最后或没有该元素。

如何计算时间的递归函数的复杂性?

递归函数一般可以写成一个数学递推关系。为了计算时间复杂度,我们必须知道如何解决递归公式,这个问题将在后面讨论。

参考:http://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  3. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。