大 O 算法

在算法和数据结构领域，一般使用时间复杂度分析的方式来检验代码的性能。时间复杂度分析本身是一个相对理论化的领域，如果真要研究它的话，里面涉及大量数学的内容和一些新的概念，如果不是专门从事这方面工作的人，研究的这么深入意义不大，所以本文也只是相对简单的说一下时间复杂度是怎么一回事，让大家有个相对感性的认识即可。当然了，如果看完本文之后还能对简单的算法进行一些时间复杂度分析那就更好了。

时间复杂度到底是怎么一回事?

通常我们会说一个算法的时间复杂度是 O(1), O(n), O(logn), O(nlogn), O(n^2) 等。这其实就是时间复杂度，简单的来说大 O 描述的是算法的运行时间和输入数据之间的关系。

看如下代码:

public static int sum(int[] nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    return sum;
}

该代码的时间复杂度是 O(n) ，那如何得出这个结论的呢？下面简单分析一下：

O(n) 指的是该代码运行时间的多少和 n 的大小成线性关系的(其中 n 是数组元素的个数)，既然是线性关系，那为什么要用大O，叫做 O(n) 呢？

数学中的线性关系是: y = a * x + b (a, b均是常数)，上过初中的应该都知道这个公式。而 O(n) 其实是在线性方程的基础上忽略了很多常数。

在上面的 for 循环的代码中，我们首先要将数组中的元素取出来，其次是把 sum 的值取出来，再把 sum 和元素 num 的值加在一起，再把相加的结果赋值给 sum。针对数组中的每个元素都要进行如上操作，如上操作也就是线性方程中的常数 a。在 for 循环开始前，还要为 sum 开辟内存空间，并将 0 赋值给 sum，等 for 循环结束之后，还要将结果返回，这些步骤可以理解为线性方程中的 b 。

在实际算法分析时，如果也把 a 和 b 的时间消耗也分析出来，一方面是必要性不大的，另一方面是有时也是不可能的，因为编译器不一样，生成的指令也不一样，CPU 的架构不一样，所执行指令的时间也不一样，所以很难分析出具体的时间是多少。所以在时间复杂度分析时，我们时常是忽略掉常数的，忽略常数也就意味着，如下：

序号	线性方程	时间复杂度
1	T = 2 * n + 2	O(n)
2	T = 2000 * n + 10000	O(n)
3	T = 1 n n + 0	O(n^2)
4	T = 2 n n + 200 * n + 10	O(n^2)

如上表格，第一个和第二个虽然常数值差距很大，但是其时间复杂度是一样的。第二个和第三个的常数差距也比较大，但是第三个的时间复杂度却是 O(n^2) 的，也就是说第三个的性能是比前两个性能低。但是我们可能有疑问了，如果 n = 10 的话，第二个消耗的时间是 30000，而第三个消耗的时间是 100，明显第三个快。

事实也是如此, 如果一个算法是 O(n) ，另一个算法是 O(n^2) 并不是说对应任意输入来说 O(n) 一定要快于 O(n^2) ,具体的确需要看常数的值。

但是大O其实是表示的一种渐进时间复杂度，也就是描述的当 n 趋近于无穷的时候，两个算法谁快谁慢，例如第四个线性关系表达式，当 n 趋近于无穷的时候，低阶项的影响可以忽略不计了，所以时间复杂度也是 O(n^2) 。

在实际的开发中，在n 较小的情况下，很多高阶算法因为常数比较小，可能会快于低阶算法。

综上所述，大O描述的是一个算法的渐进时间复杂度，也就是说该算法消耗的时间和输入数据规模之间的关系。