在讲复杂度分析之前，先理一下，什么是数据结构与算法，以及数据结构与算法之间的关系。
什么是算法与数据结构
数据结构，是指一组数据的存储结构；算法，就是操作一组数据的方法。
数据结构和算法，是相辅相成的。数据结构，是为算法服务的；算法，是要作用在特定的数据结构之上。
使用不同的算法，解决同一个问题，效率可能相差非常大。
比如，求第n个斐波那契数(fibonacci number)
/**
* 斐波那契数，当前项为前两项之和
* 0 1 1 2 3 5 8 13 ...
*/
// 递归
public static int fib1(int n) {
if (n <= 1) {
return n;
}
return fib1(n - 1) + fib1(n - 2);
}
// 循环遍历
public static int fib2(int n) {
if (n <= 1) {
return n;
}
int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i++) {
int sum = first + second;
first = second;
second = sum;
}
return second;
}
public static void main(String[] args) {
int n = 45;
Times.test("fib1", new Task() {
public void execute() {
System.out.println(fib1(n));
}
});
Times.test("fib2", new Task() {
public void execute() {
System.out.println(fib2(n));
}
});
}
打印结果为：
【fib1】
开始：22:16:05.335
1134903170
结束：22:16:11.663
耗时：6.328秒
-------------------------------------
【fib2】
开始：22:16:11.666
1134903170
结束：22:16:11.666
耗时：0.0秒
-------------------------------------
第一种算法，耗掉了6.328秒！第二种算法，几乎瞬间完成。
如何评判一个算法的好坏？
如果单从执行效率上进行评估，可能会想到这么一种方案：比较不同算法对同一组输入的执行处理时间。这种方案叫做事后统计法，上面的测试用例，就是采用了此方案。
不过，这种方案有非常大的局限性：
- 执行时间严重依赖硬件以及运行时各种不确定的环境因素
- 必须编写相应的测算代码
- 测试数据的选择比较难以保证公正性，比如对小规模的数据排序，插入排序可能会比快速排序更快。
因此，我们需要一个不用具体测试数据来测试，就可以粗略估计算法执行效率的方法：时间复杂度分析法和空间复杂度分析法。
- 时间复杂度（time complexity）:估算程序指令的执行次数（执行时间）
- 空间复杂度（space complexity）:估算所需占用的存储空间
一般从以下维度来评估算法的优劣：
- 正确性
- 可读性
- 健壮性（对不合理输入的反应能力和处理能力）
大O表示法（Big O）
一般用大O表示法来描述复杂度，它表示的是数据规模n对应的复杂度
忽略常数、系数、低阶
- 9 –> O(1)
- 2n + 3 –> O(n)
- n^2 + 2n + 6 –> O(n^2)
- 4n^3 + 3n^2 + 22n + 100 –> O(n^3)
注意：大O表示法，只是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率
常见的复杂度
- 常数阶 –> O(1)
- 线性阶 –> O(n)
- 平方阶 –> O(n^2)
- 对数阶 –> O(logn)
- 线性对数阶 –> O(nlogn)
- 立方阶 –> O(n^3)
- 指数阶 –> O(2^n)
数据规模较小时
数据规模较大时
规模较大时，复杂度从小到大 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
斐波那契数复杂度分析
在前面，我们用了递归和循环遍历的方法，分别求出第n个斐波那契数。
- 递归方法时间复杂度分析
O(fib1(n)) = O(2^0 + 2^1 + ... + 2^(n-2)) = O(2^(n-1) - 1) = O(0.5 * 2^n - 1) = O(2^n)
所以时间复杂度是O(2^n)，呈现指数级增长趋势
- 循环遍历方法时间复杂度分析
O(fib2(n)) = O(2 + (n - 1)) = O(n + 1) = O(n)
所以时间复杂度是O(n)，呈线性增长趋势
从时间复杂度可以明显看出，两者的增长趋势。这也是两者时间消耗相差巨大的原因。
算法的优化方向
- 用尽量少的存储空间
- 用尽量少的执行步骤（执行时间）
- 根据情况：
- 空间换时间
- 时间换空间
