我眼中的算法
- 算法和数据结构是计算机科学的基石，它很重要！
- 数据结构四大法宝：array 、linked list 、hash table、binary tree！
- 选择合适简单的算法，调用优秀的库，比玩弄高级的理论更有意义。玩弄高级算法和数据结构，更多的成为了迎合面试官的工具！！！
大O记法
O(f(n))
- 基本参数 n : 数据规模，如待检索的数据量。
- f(n) ： 将复杂性或运行时间表达为n的函数，如 logn。
- O 表示量级（order)。
- 实例：二分检索是O(logn)，表示需要通过logn量级的步骤去检索一个规模为n的数组。
- 细节：
5.1. f(n)函数表示量级，会去掉常数和低量级。
5.2. 这种渐进估算在实践中可能存在差异，通常n较小时，复杂的算法很慢。
5.3. 应该区分最坏情况和期望情况，期望的情况依赖于对输入的假定。如：快速排序最坏情况为O(n^2)，期望情况为O(nlogn)。
常见案例
| 案例 | 类型 | 记法 |
|---|---|---|
| 下标访问数组 | 常数 | O(1) |
| 二分检索 | 对数 | O(logn) |
| 字符串比较 | 线性 | O(n) |
| 快速排序 | nlogn | O(nlogn) |
| 简单排序 | 平方 | O(n^2) |
| 矩阵算法 | 立方 | O(n^3) |
| 集合划分 | 指数 | O(2^n) |
网友评论