算法的复杂度

什么是算法

算法是用于解决特定问题的一系列的执行步骤，使用不同算法，解决同一个问题，效率可能相差非常大

如何评判一个算法的好坏？

如果单从执行效率上进行评估，可能会想到这么一种方案：比较不同算法对同一组输入的执行处理时间，这种方案也叫做：事后统计法。

上述方案有比较明显的缺点：执行时间严重依赖硬件以及运行时各种不确定的环境因素，必须编写相应的测算代码，测试数据的选择比较难保证公正性

一般从以下维度来评估算法的优劣

正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）

时间复杂度（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表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率

对数阶的细节

对数阶一般省略底数 log2(n) = log2(9) ∗ log9(n) 所以 log2(n) 、log9(n) 统称为 log(n)

---

常见的复杂度

◼ 可以借助函数生成工具对比复杂度的大小

◼ https://zh.numberempire.com/graphingcalculator.php

数据规模较小时

数据规模较大时

fib函数的时间复杂度分析

// O(2^n) public static int fib1(int n) { if (n <= 1) return n; return fib1(n - 1) + fib1(n - 2); } // O(n) 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; }

fib函数的时间复杂度分析

fib函数的时间复杂度分析

算法的优化方向

◼ 用尽量少的存储空间 ◼ 用尽量少的执行步骤（执行时间） ◼ 根据情况，可以 ◼ 空间换时间 ◼ 时间换空间