一、为什么要有大O记号？

谈到大O记号，有一个问题就是为什么需要通过大O记号来衡量一段代码的时间复杂度呢？通过直接运行代码无法衡量程序的性能吗？

答案是肯定的，但是通过运行代码来衡量性能是不全面的，一些情况下甚至不具备可操作性。比如以下几点

• 测试用例可能无法完整的覆盖每一种情况，一个算法的表现在输入不同时不一定是稳定的表现，可能会有很大的差异，此外测试环境自身（操作系统、硬件等）也会影响程序的表现。
• 无法模拟出真实情况，比如在数据量很大很大的情况下，表现会如何？有的情况可能在真实的线上环境才会遇到。

通过过大O记号能够更加快速、简单、有效的衡量一个算法的好坏。

陶渊明和Turing的说法更能让人意会。

好书不求甚解，每有会意，便欣然忘食。

陶渊明

Mathematics is more in need of good notations than of new theorems.
对于数学而言最急需的与其说是一个又一个新发现的定理，不如说是一个好的记号.

Alan Turing

二、如何使用大O记号衡量一段代码的时间复杂度呢？

在使用大O记号前，需要先量化一下时间度量的最小单位，也就是一个unit_time，通常我们把一个读写，或者运算操作统一看做为一个unit_time，而衡量算法的时间复杂度，就是衡量一共执行了多少个unit_time。

举个栗子，以下代码的时间复杂度是多少呢？

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

从代码中可以看到，消耗1个unit_time时间对1个变量赋值之后，for循环中代码加上for循环本身被执行了n * 2次，每次执行1次消耗1个unit_time时间。那么这段代码消耗的时间就是 2n + 1个unit_time，对应的就是 T(n) = (2n + 1) * unit_time 的时间。虽然unit_time的值是不清楚的，但是执行时间T(n)与与代码执行次数n成正比是明确的。

总结成一个公式就是 T(n) = O(f(n))

大O记号并不直接表现算法的执行时间，而是指代码执行时间随着输入数据的增长而变化的趋势，所以也叫作渐进时间复杂度（ asymptotic time complexity ），简称时间复杂度。

但是对于开始的那个变量赋值操作，我们把他看做一个常数级的操作，对于n前面的那个2我们也把它看作为一个常数，它并不太影响整个算法的好坏，对于这样的常数项，无论有多少都可以被省略掉，所以算法最终的复杂度就是 T(n) = O(n)。

但是对于下面这样的情况复杂度又是多少呢？

function t($n){
    for ($i = 0; $i < $n; $i++){
        test($n);
    }
}

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

可以看到，test函数被执行n次，而test函数内的for循环也被执行了n次，那么这个函数的时间复杂度就是，O(n^2)。

那这种呢？

function logn($n){
    $num = 1;
    while ($num < $n){
        $num *= 2;
    }
}

可以看到 num 的值在呈指数级上升，while循环被执行的次数则是 log N，这类时间复杂度也是比较常见的一种，在归并排序，二叉树中都能看到。

时间复杂度大概可以从三个方面来关注：

• 执行次数最多的代码
• 总复杂度取决于量级最大的那段代码的复杂度
• 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

三、不同情况下的时间复杂度分析

通常来说，通过大O衡量了一个算法的时间复杂度就可以获取到这个算法的效率，但这还是不够全面的。时间复杂度还可以进一步从最好情况、最坏情况、平均情况、均摊 4个维度来拆解。

先来看一段代码：

function add($arr, $item){
    foreach ($arr as $val){
        if ($val === $item){
            return $item;
        }
    }
    return -1;
}

这段代码的时间复杂度的多少呢？很容易看出来答案是 O(n)，但是应用到工程当中实现的时候，每一次调用都O(n)吗？显然这里面也有运气的成分，运气好的时候第一个就找到了，运气不好的时候找到最后一个都不是。针对这的情况该如何提前衡量这个算法呢？

最好情况时间复杂度（best case time complexity）
顾名思义就是这个算法在最好情况下的复杂度，当数组第一个元素就能命中时，复杂度为 O(1)。

最坏情况时间复杂度(worst case time complexity)
顾名思义就是算法在最坏情况下的复杂度，当数组最后一个元素才能命中时，复杂度是O(n)。

平均时间复杂度(avg case time complexity)
平均复杂度的分析会麻烦一些，因为需要考虑到所有的情况，然后求出平均值。假设数组的长度是n，命中的概率为 1/(n+1) ，此时平均复杂度是多少呢？n种情况的复杂度之和除以n，则是 O((1 + 2 + 3 … + (n + 1))/ n)，去掉常数项之后则是O(n)。注意这里分析的情况是未命中元素只有一个，如果有一半的元素无法命中呢？或者有其他更多的情况无法命中呢？如果考虑到不同的情况，那么计算就引入了概率论中的加权平均值，平均时间复杂度也可以称为加权平均时间复杂度。

均摊时间复杂度(amortized time complexity)
均摊时间复杂度用的比较少，对应的分析方法叫摊还分析（或平摊分析）它也可以说是平均时间复杂度的一种特殊情况，看看这个代码。

function insert($num){
    static $arr = [0];
    $maxLen = __N__;

    if (count($arr) == $maxLen){
        $total = 0;
        foreach ($arr as $v){
            $total += $v;
        }
        $arr = [];
        $arr[0] = $total;
    }
    $arr[] = $num;
    return $arr[0];
}

这段代码中的数组，当数组的元素个数到达一定数目时就会自动求和并清空数组，那么这个算法的平均复杂度是多少呢？按照上述的平均复杂度的方法分析所有的情况也是可以的，不过我们注意到了这个算法是有规律可循的，在经过了n-1次插入之后必然会有一次循环计算，这个周期就可以代表所有的情况，每次O(1)的操作均摊到n次，则是O(1/n)，最后一次是O(n/n)，那么均摊时间复杂度就是 O(1/n + 1/n … + n/n) ，则就是O(1)。针对这样的有规律的特殊场景，使用的这种更简单的分析方法叫摊还分析法，通过摊还分析法得到的时间复杂度，叫均摊时间复杂度。

四、空间复杂度

空间复杂度相对与时间复杂度来说比较好理解，时间复杂度全称叫渐进时间复杂度，表示算法执行时间与数据规模的增长关系。空间复杂度全称叫渐进空间复杂度，表示算法执行占用空间与数据规模之间的增长关系。

五、复杂度分析的一些其他感悟

大O记号我们提供了一种更简单的方法去衡量一个算法好坏，尽管大O并不是那么精细，以至于同一级别的算法在工程应用时也会有数倍的差异。但是在算法研究领域，常数倍是一个不大的差别，因为他们同处于一个数量级，这部分是需要工程人员在应用的时候去关心的。不过大O却为我们观察别的事物也带来了启发意义，想到人一生会遇到很多的选择，小到买菜、吃饭的几十块钱，大到结婚、工作定居，对于前者我们总是清晰的一眼就能看出利弊来，而对于后者却常常只能看到三寸之远。如果站在大O的角度出发，抛开细枝末节，关注最具代表性，最重要的东西，就能够快速的为当前事物画出上边界和下边界，定位出不同事物所处的量级，再决定是否要采用，用哪一个，然后再考虑怎么用的问题，不至于一开始就被细枝末节所烦恼，反而忘了关注最本质的东西。