[数据结构]学习笔记二 - pod4g/tool GitHub Wiki

1. 算法

算法是解决特定问题的步骤

2. 算法的要求

2.1 基本要求

1. 输入
2. 输出
3. 有穷性
4. 可行性
5. 确定性

2.2 更高的要求

1. 正确性
2. 可读性
3. 健壮性
4. 时间用的少，存储用的少

3. 算法的衡量标准

1. 事后统计（不科学、不方便）
2. 事前分析（忽略掉计算机软硬件等因素，只看算法采用的策略和步骤）

4. 大O推导

对于f(n)和g(n)，如果存在一个数N，使得所有 n > N，都有f(n) > g(n)，我们我们就说f(n)的增长快于g(n)

忽略常数、忽略低阶、忽略倍数，只看最高阶，因为随着问题规模n的增大，基本操作也越来越大，那么到最后会发现，常数、低阶、倍数等对函数增长的影响越来越小，到最后可以忽略不计

5. 阶

常数阶：O(1) 线性阶：O(n) 对数阶：O(logn) 平方阶：O(n^2) 立方阶：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)