一、大O表示法（Big O）
- 一般用大 O 表示法来描述复杂度，它表示的是数据规模 n 对应的复杂度。
- 忽略常数、系数、低阶
9>>O(1)
2n + 3>>O(n)
n^2 + 2n^2 + 6>>o(n^2)
4n^3 + 3n^2 + 22n + 100>>O(n^3) - 注意： 大 O 表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率。
| 执行次数 | 复杂度 | 非正式术语 |
|---|---|---|
| 12 | 常数阶 | |
| 4log2(n) + 25 | 对数阶 | |
| 2n + 3 | 线性阶 | |
| 3n + 2nlog3(n) + 15 | nlogn阶 | |
| 4n^2 + 2n + 6 | 平方阶 | |
| 4n^3 + 3n^2 + 22n + 100 | 立方阶 | |
| 2^n | 指数阶 |
- O(1) < O(longn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
- 可以借助函数生成工具对比复杂度的大小
https://zh.numberempire.com/graphingcalculator.php
对数阶的细节
- 对数阶一般省略底数
因为不管底数是什么，都可以通过转换为一个常数*log2(n)
log2(n) = log2(9) * log9(n)
又因为2为底的可以省略2。- 所以 log2(n)、log9(n)统称为log(n)
- 时间复杂度（time complexity）：估算程序指令的执行次数。这里的大O的意思是估算程序最终的执行次数是多少。
- 空间复杂度（space complexity）：估算所需占用的存储空间。
二、示例
public static void test1(int n) {
// 1
if (n > 10) {
System.out.println("n > 10");
} else if (n > 5) {
System.out.println("n > 5");
} else {
System.out.println("n <= 5");
}
// 时间复杂度
// 1 + 4 + 4 + 4
// 14
// O(1)
// 空间复杂度
// O(1)
for (int i = 0; i < 4; i++) {
System.out.println("test");
}
}
public static void test2(int n) {
// 时间复杂度
// 1 + 3n
// O(n)
for (int i = 0; i < n; i++) {
System.out.println("test");
}
}
public static void test2(int n) {
// 时间复杂度
// 1 + 2n + n * (1 + 3n)
// 1 + 2n + n + 3n^is 2
// 3n^2 + 3n + 1
// O(n^2)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
public static void test5(int n) {
// 时间复杂度
// 8 = 2^3
// 16 = 2^4
// 3 = log2(8)
// 16 = log2(16)
// log2(n)
// O(logn)
while ((n = n / 2) > 0) {
System.out.println("test");
}
}
public static void test7(int n) {
// 时间复杂度
// 1 + 2*log2(n) + log2(n) * (1 + 3n)
// 1 + 3*log2(n) + 2 * nlog2(n)
// O(logn + nlogn)
// O(nlogn)
for (int i = 1; i < n; i = i* 2) {
// 1 + 3n
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
三、算法的优化方向
- 用尽量少的存储空间
- 用尽量少的执行步骤（执行时间）
- 根据情况，可以
空间换时间
时间换空间
