时间复杂度和空间复杂度

第二节时间复杂度、空间复杂度

O(1): Constant Complexity 常数复杂度

O(log n): Logarithmic Complexity 对数复杂度

O(n): Linear Complexity 线性时间复杂度

O(n^2): N square Complexity 平方

O(n^3): N cubic Complexity 立方

O(2^n): Exponential Growth 指数

O(n!): Factorial 阶乘

注意：只看最高复杂度的运算

时间复杂度和空间复杂度

计算：1 + 2 + 3 + … + n

• 方法一：从1到n的循环累加——（O(n)的复杂度） y = 0 for i = 1 to n: y += i

• 方法二：求和公式 sum = n(n+1)/2——（O(1)复杂度，因为只执行1次） y = n * (n + 1) / 2

更复杂的情况：递归

Fib: 0, 1, 1, 2, 3, 5, 8, 13, 21, ……

• F(n) = F(n - 1) + F(n - 2)

• 面试（直接用递归）——不建议，可以缓存重复数据提高性能 int fib(int n) { if (n < 2) return n; return fib(n - 1) + fib(n - 2); }

时间复杂度和空间复杂度

二叉树遍历 - 前序、中序、后序：时间复杂度是多少？——O(n)

图的遍历：时间复杂度是多少？——O(n)

搜索算法：DFS、BFS 时间复杂度是多少？——O(n)

二分查找：时间复杂度是多少？——O(logn)