大 O 复杂度表示法

大 O 时间复杂度表示法

公式：T(n) = O(f(n))

分析：

function sum($n){
    $sum = 0;
    for ($i=0; $i<$n; $i++) {
      $sum += $i;
    }
    return $sum;
}

假设上述代码每行执行时间相同，都为unit_time，第2行需要 1 个unit_time的时间，3、4 都执行了 n 遍，都需要 n 个unit_time的时间，所以这代代码总执行时间为 (2n + 1) * unit_time 的时间。

function mul($n){
    $res = '';
    for ($i=1; $i<=$n; $i++) {
        for ($j=1; $j<=$i; $j++){
            $res .= $j . ' * ' . $i . ' = ' . $i*$j . '&nbsp;';
        }
        $res .= "<br>";
    }
    return $res;
}

这是一个99乘法表，安装之前的示例继续分析一下代码执行时间：
第2行需要1个unit_time的时间，第3、7行都需要n个unit_time时间，第4、5行都需要n^{2}个unit_time的时间，所以这段代码总执行时间为 (n^{2} 2n + 1) unit_time 时间。

从上面两段代码中可以看出，代码的总执行时间 T(n) 与每行代码的执行次数 n 成正比。

公式：T(n) = O(f(n))中，T(n) 是代码总执行时间，n 代表数据规模大小，f(n) 代表代码执行次数总和，O 代表T(n) 与 f(n) 成正比。

第一段代码中 T(n) = O(2n + 1)，第二段代码中 T(n) = O(n^{2} * 2n + 1)

这就是大O时间复杂度表示法，它并不代表代码的真正执行时间，而是代码执行时间随数据规模增长的变化趋势。

因为这是一种变化趋势，所以我们通常忽略公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。
我们在分析一段代码时间复杂度的时候只需要关注循环次数最多的那段代码就可以了。

所以，上述第一段代码 T(n) = O(n)，第二段代码 T(n) = O(n^{2})

几种常见的时间复杂度

常量阶 O(1)
对数阶 O(logn)
线性阶 O(n)
线性对数阶 O(nlogn)
平方阶 O(n2)
立方阶 O(n3)

O(m+n)

除了上面几种常见的还有这种由两种数据规模决定的复杂度

function sum($m, $n){
    $sum = 0;
    $diff = 0;
    for ($i=0; $i<$n; $i++) {
      $sum += $i;
    }

    for ($j=0; $j<$m; $j++) {
      $sum -= $j;
    }

    return $sum + $diff;
}

向这种有两种未知的量级，不能简单的相加省略掉一个，所以上面代码的时间复杂度就是 O(m+n)

大 O 空间复杂度表示法

空间复杂度和时间复杂度类似，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

function format($list){
    $result = [];
    foreach($list as $item){

        ...// 处理一些数据

        $result[] = $item;
    }
    return $result;
}

和分析时间复杂度一样，空间存储变量 $result 和数据规模 $list 有关，其它的代码没有占用更多的空间，所以空间复杂度为 O(n)。

常见的空间复杂度有 O(1)、O(n)、O(n^{2})