在开始二刷前，先走出舒适区，硬啃一波性能分析。尽可能用人话说清楚复杂度究竟是个啥玩意。
时间复杂度
什么是时间复杂度
顾名思义，时间复杂度（也作渐进时间复杂度）就是描述算法运行时间的函数。通常会用操作单元数量来代表程序消耗的时间，默认CPU的每个单元运行消耗的时间都是相同的。
举个例子，假设算法问题的规模为n，那么操作单元数量便用函数f(n)来表示，随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，记为O(f(n))。乂，这里引入了一个新的字母O，这是啥呢？
什么是大O
大O用来表示上界，上界就是算法最坏情况的运行时间，即任意数据输入的运行时间最大为大O。
俗话说的好，抛开输入数据形式来考虑运行时间就是耍流氓。拿插入排序来说，在数据有序的情况下运行时间是O(n)，但当数据是逆序，插入排序的运行时间就是O(n²)，因此插入排序的时间复杂度是O(n²) 。这不是我说的，是算法导论规定的（
这时候杠精就会说，乂，快速排序的时间复杂度是O(nn)，但是在数据已经有序的情况下，它的运行时间不是是O(n²) 嘛？确实，严格从大O的定义来讲，快速排序的时间复杂度应该是O(n²)。业内的默认规定大O代表的就是一般情况。
毕竟你都有序了，还排它干嘛呢
不同数据规模的差异
时间复杂度定义为O(f(n))。从数学上考虑f(n)，当它含有常数项且数据规模很小时，甚至用O(n²)的算法比用O(n)的更合适。但是，经常有题解会说：”忽略常数项之后，O(n)优于O(n²)“，这是为啥呢？
这又涉及到大O的定义，大O就是数据量级非常大的情况下所表现出的时间复杂度，此时常数项系数已不起决定性作用。
给出常见的比较：O(1) < O(n) < O(n) < O(n
n) < O(n²) < O(n³) < O(2
) < O(n!)
顺便提一嘴，学过数学的都知道，f(n)可以简化，例如后面的式子中如果包含前面的式子，那也可以忽略。
O(
n)以什么数为底？
这时候，学数学的同学要问了：乂，平时说某算法的时间复杂度是n的，那么一定是以2为底n的对数么？
这个同学数学学的相当好，在数学中，是不存在没有底数的对数表达式的。但是在编程的世界里，有一种忽略底数的描述。举个例子，假如有两个算法，它们的时间复杂度分别是n和
n。根据高中数学，
n=
10 *
。
10是一个常数，大O中常数项可忽略。由此可见，大O中，任何底数其实都是一个玩意，所以可以将其忽略。
超时测试实验结果
任何开发计算机程序员的软件工程师都应该能够估计这个程序的运行时间是一秒钟还是一年。对于计算机硬件要至少有大概的概念，这也是为啥力扣的提示中提示各种数据范围和时间限制，要会根据这些提示估计程序的时间复杂度大概是多少，再采取符合要求的算法。
直接给出大致的实验结果，数字代表对应时间复杂度的算法每秒能运行的次数：（一定不是我懒得自己敲一遍）O(n)：、O(n²)：
、O(n
n)：
。
空间复杂度
和时间类似，空间复杂度也可以用O(f(n))来表示。采用此种办法可以对程序运行中需要多少内存进行估计。
常见问题
第一个常识是——空间复杂度是考虑程序运行时占用内存的大小，而不是可执行文件的大小。
第二个常识是——很多因素会影响程序真正使用的内存，所以空间复杂度仅仅是个大体的预估。
第三个常识是——O(1)、O(n)等空间复杂度都好理解，而O(n)的空间复杂度在递归算法中出现。
Java的内存管理
Java依赖内置虚拟机来做内存管理，因此不需要程序员去考虑内存泄漏的问题。
顺便引入一下内存对齐的概念，在Java八股中很少提到，了解一下。跨平台的编程语言都需要做内存对齐，其实并不仅限于C语言，当然内存对齐还有助于大幅度提高运行速度。
CPU读取内存不是一次读取单个字节，而是一块一块的来读取内存，块的大小可以是2，4，8，16个字节，具体取多少个字节取决于硬件。在存储数据时，如果划分的是四字节，而实际数据只占用一字节，那么多余的三字节就被浪费了。但是在读取过程中，每次读对应的地址位置即可，而不需要读多个，再裁剪、拼贴。所谓的内存对齐，就是牺牲空间，换取时间。
递归分析
接下来，就用最难分析的递归算法为例，总结一下算法性能的分析方法。
求x的n次方
譬如，现在你在面试阿里云，面试官出了一道题：求x的n次方。这还不简单，秒写出如下代码：
int result = 1; // 注意 任何数的0次方等于1
for (int i = 0; i < n; i++) result = result * x;
return result;
此时，面试官问，有无效率更高的算法呢？这时候马上想到了递归，开写！
int function(int x, int n) {
if (n == 0) return 1; // return 1 同样是因为0次方是等于1的
return function(x, n - 1) * x;
}
面试官微微一笑，问：此代码时间复杂度是多少呢？递归嘛，复杂度肯定是O(n)，你这么答，遂寄。
递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数。每次n-1，递归了n次时间复杂度是O(n)，每次进行了一个乘法操作，乘法操作的时间复杂度是一个常数项1，所以这份代码的时间复杂度是 n × 1 = O(n)。
正确的标准答案如下，利用了等比数列的求和公式，抽取出了递归操作：
int function(int x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
int t = function(x, n / 2);//若将此式子放入判断语句中，则复杂度仍为O(n)
if (n % 2 == 1) {
return t * t * x;
}
return t * t;
}
仅仅有一个递归调用，且每次都是n/2 ，所以一共调用了log以2为底n的对数次。这么答，面试官应该是很满意的，但是初见的同学会感觉非常抽象。接下来用图表详细说明。
| 参数n的大小 | 递归调用k次 |
|---|---|
| 2 | 2 |
| 4 | 3 |
| 8 | 4 |
显然有如下公式：，转换形式之后可得：
。又因为每次递归都是一次乘法操作，它的时间复杂度即为O(
n)。
斐波那契数列
动态规划刷的第一道题就是此题，代码基本都能背出来了：
int fibonacci(int i) {
if(i <= 0) return 0;
if(i == 1) return 1;
return fibonacci(i-1) + fibonacci(i-2);
}
非常简单的式子，但是每次递归有1次加法，有2个递归调用（这里采用2叉树分析）。其复杂度为O()，很明显太大了。
那就减少一下递归的调用次数呗：
int fibonacci(int first, int second, int n) {
if (n <= 0) return 0;
if (n < 3) {
return 1;
} else if (n == 3) {
return first + second;
} else {
return fibonacci(second, first + second, n - 1);
}
用first和second来记录当前相加的两个数值，此时就不用两次递归了。只是递归了n次，所以时间复杂度是O(n)。递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度。从代码中可以看出每次递归所需要的空间大小都是一样的，它需要的空间是一个常量，并不会随着n的变化而变化，每次递归的空间复杂度就是O(1)。
递归第n个斐波那契数的话，递归调用栈的深度就是n（又是二叉树的知识，画图！）。每次递归的空间复杂度是O(1)， 调用栈深度为n，所以这段递归代码的空间复杂度就是O(n)。
总结
对于时间和空间复杂度有了最基本的了解，以后每刷一题，都要学会自己分析其性能。
