复杂度分析方法与陷阱

一、面试常考点

1. 如何分析循环

串行相加、嵌套相乘、递归看递推式。

2. 常见误区

忽略最坏情况、把均摊和单次复杂度混淆。

二、细节介绍

1. 递归复杂度

通过主定理或递推展开估算。

2. 均摊复杂度

如动态数组扩容，单次可能 O(n)，均摊仍 O(1)。

三、示例代码

function binarySearch(arr, target) {
  let l = 0
  let r = arr.length - 1
  while (l <= r) {
    const mid = l + ((r - l) >> 1)
    if (arr[mid] === target) return mid
    if (arr[mid] < target) l = mid + 1
    else r = mid - 1
  }
  return -1
}
// 时间 O(log n), 空间 O(1)

四、常用应用场景

1. 方案选型

多方案取舍时用复杂度做第一层筛选。

2. 性能预估

上线前估算数据规模上限是否可承受。