前面我们说了算法的重要性数据结构与算法开篇，今天我们就开始学习如何分析、统计算法的执行效率和资源消耗呢？请看本文一一道来。
数据结构和算法本生解决的就是「快」和「省」的问题，那就是如何让代码跑得快，还能节省存储空间。打造一台法拉利，不仅跑得快还省油，拥有好的算法与数据结构，程序跑得快，还省内存并且长时间运行也不会出故障，就像跑车长时间运行车子也不会出现异常「车震」，同时还快。所以赶紧上车，一起学习数据结构与算法，赶紧上车「稳稳」的学会如何检测跑车到底快不快，省油不省油。
这里就要用到我们今天要讲的内容：时间、空间复杂度分析。只要讲到数据结构与算法，就一定离不开时间、空间复杂度分析。复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。这就就像内功心法，上乘武功还需搭配牛逼心法。
只有学会了检测标准才能在设计的时候心中按照标准来编写打造我们的「法拉利」代码。
为何需要复杂度分析可能会有些疑惑，我把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢？这种分析方法能比我实实在在跑一遍得到的数据更准确吗？
这种属于非要自己去尝试，没有根据合理方法预测我们要的就是像算命大师一样预先知道。很多数据结构和算法书籍还给这种方法起了一个名字，叫事后统计法。但是，这种统计方法有非常大的局限性。
1. 测试结果非常依赖测试环境
测试环境中硬件的不同会对测试结果有很大的影响。比如，我们拿同样一段代码，分别用 Intel Core i7 处理器和 Intel Core i3 处理器来运行，不用说，i7 处理器要比 i3 处理器执行的速度快很多。
就好像同一辆车放在深圳北环大道与我家农村小山沟跑是不一样的。
2.测试结果受数据规模的影响很大
后面我们会讲排序算法，我们先拿它举个例子。对同一个排序算法，待排序数据的有序度不一样，排序的执行时间就会有很大的差别。
极端情况下，如果数据已经是有序的，那排序算法不需要做任何操作，执行时间就会非常短。除此之外，如果测试数据规模太小，测试结果可能无法真实地反应算法的性能。
比如，对于小规模的数据排序，插入排序可能反倒会比快速排序要快！
所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。这就是我们今天要讲的时间、空间复杂度分析方法。
大 O 复杂度表示法算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？就像检测车子马力与油耗似的。
求 1,2,3…n 的累加和。现在，一起估算一下这段代码的执行时间。
int cal(int n) { int sum = 0; int i = 1; for (; i <= n; ++i) { sum = sum + i; } return sum; }从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据。尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样，但是，我们这里只是粗略估计，所以可以假设每行代码执行的时间都一样，为 unit_time单位时间。
在这个假设的基础之上，这段代码的总执行时间是多少呢？
第 2、3 行代码分别需要 1 个 unit_time 的执行时间，第 4、5 行都运行了 n 遍，所以需要 2n*unit_time 的执行时间，所以这段代码总的执行时间就是 (2n+2)*unit_time。可以看出来，所有代码的执行时间 T(n) 与每行代码的执行次数成正比。
我们继续分析下面这段代码
int cal(int n) { int sum = 0; int i = 1; int j = 1; for (; i <= n; ++i) { j = 1; for (; j <= n; ++j) { sum = sum + i * j; } } }我们依旧假设每个语句的执行时间是 unit_time。那这段代码的总执行时间 T(n) 是多少呢？
第 2、3、4 行代码，每行都需要 1 个 unit_time 的执行时间，第 5、6 行代码循环执行了 n 遍，需要 2n * unit_time 的执行时间，第 7、8 行代码循环执行了 n^2^遍，所以需要 2n^2^ * unit_time 的执行时间。所以，整段代码总的执行时间 T(n) = (2n^2^+ 2n + 3)*unit_time。
尽管我们不知道 unit_time 的具体值，但是通过这两段代码执行时间的推导过程，我们可以得到一个非常重要的规律，那就是，==所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比==。
我们可以把这个规律总结成一个公式。注意，大 O 就要登场了！
$T(n) = O(f(n))$