复杂度反证训练别只会背 Big O 结论一、复杂度要能解释很多题解会写时间复杂度 O(n)、空间复杂度 O(1)但问为什么就说不清。复杂度不是题解末尾的装饰它是算法能不能通过约束的核心证据。面试里背结论不够最好能用反证和边界推导说明为什么不能更低、为什么不会更高。复杂度训练要从“写结果”变成“讲得清”。二、先建立推导路径flowchart TD A[输入规模] -- B[循环次数] B -- C[数据结构操作成本] C -- D[总时间复杂度] D -- E[约束是否可接受]分析复杂度时先看输入规模再看每层循环、每个操作的成本。哈希表、堆、排序、图遍历都不能只按感觉写。complexity_checklist: count_loops: true count_data_structure_ops: true include_sort_cost: true compare_with_constraints: true有清单才不容易漏掉隐藏成本。三、用反证理解下界def two_sum_bruteforce(nums, target): for i in range(len(nums)): for j in range(i 1, len(nums)): if nums[i] nums[j] target: return [i, j]暴力解是 O(n²)哈希表解是 O(n)。为什么不能 O(1)因为至少要读取输入否则无法知道数组里有什么。这个下界很简单但能帮助建立复杂度直觉。有些题必须排序是因为答案依赖全局顺序有些题可以线性是因为只需要局部状态。反证训练就是问如果更低复杂度哪些信息会来不及被读取或比较四、警惕隐藏复杂度Python 切片、字符串拼接、列表删除、堆操作、递归栈都可能把复杂度悄悄抬高。题解里如果只看显式循环很容易写错。# 每次切片都会复制递归里这样写可能不是 O(n) left arr[:mid] right arr[mid:]还要看摊还复杂度。动态数组 append 通常摊还 O(1)哈希表查询通常均摊 O(1)但它们都有条件。写题解时可以写均摊但要知道假设是什么。空间复杂度也不能忽略。递归深度、辅助数组、哈希表、队列峰值都要算。很多 BFS 题时间 O(n)空间也是 O(n)不是 O(1)。最后把复杂度和约束连起来。n100 可以 O(n³)n10⁵ 通常不行。只写复杂度不说明为什么能过约束分析就少了一半。复杂度训练还可以加入“反例解释”。比如有人把双指针内层 while 写成 O(n²)系统可以要求他说明 left 是否会回退。如果指针单调移动总移动次数就是 O(n)这比背结论更有说服力。complexity_probe: ask_pointer_monotonicity: true ask_heap_operation_count: true ask_recursion_depth: true对递归题还要区分节点访问次数和每层额外工作。一个 DFS 如果每个节点只访问一次是 O(n)如果每个节点都重新计算子树高度就可能退化成 O(n²)。最后复杂度写法要诚实。平均、最坏、摊还、期望不是一个意思。题解里写清楚假设才不会让读者误以为所有输入都一样快。五、总结复杂度反证训练要从输入规模、操作成本、隐藏开销、下界和约束一起推导而不是背 Big O。能写出 O(n) 不难能解释为什么是 O(n)、为什么不能随便更低才说明真的理解了算法。