Time Complexity Analysis

1. Summary

2. Reduction

通过O(n)的时间，把规模为n的问题变为n/2：

通过O(n)的时间，把规模为n的问题变为(2 * n/2)：

3. Time Complexity in Coding Interview

• O(1) 极少
• O(logn) 几乎都是二分法
• O(√n) 几乎是分解质因数
• O(n) 高频
• O(nlogn) 一般都可能要排序
• O(n2) 数组，枚举，动态规划
• O(n3) 数组，枚举，动态规划
• O(2n) 与组合有关的搜索
• O(n!) 与排列有关的搜索