算法的复杂度

学习如何来分析一个算法的复杂度。

为什么需要算法复杂度

为什么需要引入一个时间复杂度的概念，假设我们直接在在服务器上允许我们一个代码段通过运行时间来给出复杂度，这种方式成为事后统计法。这种方式存在什么缺陷呢？

• 受物理机影响的因素较大。如机器上某一时刻资源利用率低，就会导致你的统计存在问题
• 受数据影响较大。如排序算法，不同的数据顺序都会影响排序算法。

因此需要引入一个公式来表达数据量与算法之间的关系。

复杂度的表示方法

常用的是大O复杂度表示法。表示算法的执行效率。

T(n) = O(f(n))

• T(n) ：表示代码的执行时间。
• n：表示数据执行的大小。
• f(n)：表示每行代码执行的次数总和。

时间复杂度

规则

表示代码执行时间与数据大小直接的关系。常用的规则：

1. 只关注循环次数最多的一次的代码

   大O这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。

   for($i=0;$i<1000;$i++) {
       // do something
   }
   
   for($j=0;$i<2*$n;$j++) {
       //  do something
   }
   
   // 时间复杂度：O(n)

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

   for($i=0;$i<$n;$i++) {
       // do something
   }
   
   for($j=0;i<$n*$n;$j++) {
       //  do something
   }
   
   // 时间复杂度：O(n^2)

3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

   for($i=0;$i<$n;$i++) {
       for($j=0;$i<$n;$j++) {
           // todo
       }
   }
   
   // 时间复杂度：O(n^2)

常见的时间复杂度

按数量级异常递增

1. O(1)：

   表示常量级，即代码的执行时间与数据量没有关系。

   $a = 3;
   $b = 4;
   $sum = $a + $b;

2. O（log n）:

   如下代码，$i 即从1,2,4,8,16... 是一个等比数列，执行次数就等于 以2为底N的对数，即O（log n）。

   不管下面代码乘以2还是乘以3，时间复杂度不变。因为对数之间是可以转化的。log3n就等于log32 * log2n。因此我们忽略底数

   $i = 1;
   while(i<n) {
    $i = $i *2;
   }

3. O（nlog n）

   著名的快速排序，归并排序都是该复杂度。

4. O（m+n）, O（m*n）

   复杂度是有两个参数决定，我们无法预估这两个参数的大小

   function sumAdd($m, $n) 
   {
     for($i=0;$i<$m;$i++) {
        $m += $i
     }
   
     for($j=0;$j<$n;$j++) {
        $n += $i
     }
   
     return $m+$n
   }

分类

分类为：最好时间复杂度，最坏时间复杂度，平均时间复杂度，均摊时间复杂度。对于下面的代码时间复杂度是多少呢？

function FindIndex(array $array, $value)
{
    $index = -1;
    for($i=0;$i<len($array);$i++) {
        if ($array[$i] == $value) {
            $index = $i;
            break;
        }
    }

    return $index;
}

1. 最好时间复杂度
   在最理想的情况下，执行这段代码的时间复杂度。如上面代码最好的时间复杂度就是O(1)。

2. 最坏时间复杂度

   在最坏的情况下，执行这段代码的时间复杂度。则上面的最坏时间复杂度O(n)。

3. 平均时间复杂度（权平均时间复杂度或者期望时间复杂度）

   即概率乘以运行时间相加的结果。下图为上面代码的平均复杂度推导公式

   

4. 均摊时间复杂度

   将较高的时间复杂度的那次行为均摊到较低的时间复杂度。

   该复杂度的应用场景较少。即有规律的出现情况复杂度不一样的操作，我们可以将复杂度高的操作均摊到较低的时间复杂度上。一般均摊时间复杂度等于

   // 遍历数组插入该值与随机数，当最后一次的时候计算数组长度
   function InsertAndSum(array $array, $value)
   {
      $sum = 0;
      $n = len($array);  
      for($i=0;$i<$n ;$i++) { 
          $array[$i] = $value + mt_rand(10,100);
   
          if ($i == $n-1) {
              // 最后一次
              for($j=0;$j<$n ;$j++) {
                  $sum += $array[$j];
              }
          }
      }
   
      return $sum;
   }
   
   // 1. 循环N次中，N-1次时间复杂度都是 O(1), 1次是O(n)
   // 2. 均摊最后一次时间复杂度到前N-1次
   // 3. 得到均摊时间复杂度都是O(1)
   

空间复杂度

渐进式空间复杂度，表示数据与储存占用空间的一个关系函数。

function NewArray($n) 
{
    $a = 'cx';
    $b = new SplFixedArray($n);
    for($i=0;$i<$n;$i++) {
       $b[$i]  = $a;
    } 
}

// 这段代码的空间复杂度就是O(n), 因为在第4行申请了一个n的内存空间

常见的空间复杂度

• O(1)

  function NewArray($n) 
  {
      $a = 'cx';
      return $a;
  }

• O(n)

  function NewArray($n) 
  {
      $a = 'cx';
      $b = new SplFixedArray($n);
      for($i=0;$i<$n;$i++) {
         $b[$i]  = $a;
      } 
  }

• O(n^2)

  function NewArray($n) 
  {
      $a = 'cx';
      $b = new SplFixedArray($n*$n);
      for($i=0;$i<$n*$n;$i++) {
         $b[$i]  = $a;
      } 
  }

复杂度趋势

本作品采用《CC 协议》，转载必须注明作者和本文链接