算法分析

人们再使用计算机解决困难问题或是处理大数据时不可避免的将会产生这样的问题：

1. 我的程序运行多长时间？
2. 为什么我的程序耗尽了所有内存？

科学方法

1. 观察
2. 根据观察结果提出假设模型
3. 根据模型预测未来事件
4. 继续观察，核实预测准确性
5. 反复确认预测与观察一致

如何计算时间复杂度

先上结论：如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))。

算法的时间复杂度，用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。

显然如果 T(n) = n^2，那么 T(n) = O(n^2)，T(n) = O(n^3)，T(n) = O(n^4) 都是成立的，但是因为第一个 f(n) 的增长速度与 T(n) 是最接近的，所以第一个是最好的选择，所以我们说这个算法的复杂度是 O(n^2) 。

那么当我们拿到算法的执行次数函数 T(n) 之后怎么得到算法的时间复杂度呢？

我们知道常数项对函数的增长速度影响并不大，所以当 T(n) = c，c 为一个常数的时候，我们说这个算法的时间复杂度为 O(1)；如果 T(n) 不等于一个常数项时，直接将常数项省略。
比如
第一个 Hello, World 的例子中 T(n) = 2，所以我们说那个函数(算法)的时间复杂度为 O(1)。
T(n) = n + 29，此时时间复杂度为 O(n)。
我们知道高次项对于函数的增长速度的影响是最大的。n^3 的增长速度是远超 n^2 的，同时 n^2 的增长速度是远超 n 的。 同时因为要求的精度不高，所以我们直接忽略低此项。
比如
T(n) = n^3 + n^2 + 29，此时时间复杂度为 O(n^3)。
因为函数的阶数对函数的增长速度的影响是最显著的，所以我们忽略与最高阶相乘的常数。
比如
T(n) = 3n^3，此时时间复杂度为 O(n^3)。

常见的增长数量级函数