Big O Notation
Big O 记法描述函数渐近上界，用于分析算法时间/空间复杂度，忽略常数与低阶项。
用途
抽象算法效率的渐近增长率，比较与选择算法。
机制
f(n)=O(g(n)) 表示存在常数 C 与 n0，使 n>n0 时 |f(n)|≤C|g(n)|。常见阶：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)。关注最坏情况上界。
用例
- 算法复杂度分析
- 数据结构选型
- 性能优化决策
- 面试与教学
示例
- 输入
Binary search输出O(log n)Halves each time
常见错误
- Ignoring constant factors misjudges real-world performance
- Big O is asymptotic; benchmark for real behavior