阅读下面的 Python 函数，n 是正整数。请分析它的时间复杂度（以 total += 1 的执行次数为准）和额外空间复杂度，并说出推导过程。 ```python def h(n): total = 0 i = 1 while i <= n: for j in range(i): total += 1 i *= 2 return total ```
面试官在考什么
判断候选人是真的按循环变量的变化去累计执行次数，还是看到“外层像 log n 层、内层最多 n 次”就直接相乘。
回答框架 · 前两步
- 外层 while 的 i 取值为 1, 2, 4, …, 2^k（2^k ≤ n），共 ⌊log2 n⌋ + 1 次。
- 内层总执行次数是等比数列之和 1 + 2 + 4 + … + 2^k = 2^(k+1) − 1，不超过 2n − 1。
还有 3 条答案要点、 3 层追问、 4 个常见坑， 以及针对你简历的追问路径，在定制报告里。
延伸阅读
想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页
同一能力域的其他题
- 下面这段代码用于统计数组中和为某值的下标对： ```python def pairs(nums): s = set(nums) res = [] for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] in s: res.append((i, j)) return res ``` (1) 它的时间复杂度和空间复杂度分别是多少？请说明每一项是怎么算出来的。 (2) 如果线上 nums 的长度 n = 10^6，这个函数能不能直接上线？为什么？ (3) 如果 nums 中存在大量重复元素，复杂度会变吗？
- 有一个去重任务：内存中一次性有 1 亿条 URL，平均长度 80 个 ASCII 字符，要在一台 JVM 堆上限 4GB 的机器上做「精确去重」（不允许有误判，不允许落盘到外部存储作为主方案）。有人提议直接用 HashSet<String> 装全部 URL。请回答：(1) 估算这个 HashSet 的内存占用，判断是否可行，要求给出量级估算的过程而不只是结论；(2) 如果不可行，写出你实际会采用的方案，并说明它把成本转移到了哪里。
- 你负责一个日处理 50 亿条日志的离线去重系统。输入是 50 亿个 128-bit 的 ID，要求输出去重后的 ID 集合。团队提出两个方案：方案 A 用哈希表，期望 O(n) 时间和 O(n) 额外空间，单机 256 GB 内存可能放不下；方案 B 先外部排序再扫描去重，O(n log n) 时间和 O(1) 额外空间（磁盘），但需要多轮磁盘 I/O。作为技术负责人，你怎么做复杂度分析和工程选型？请给出量化估算和最终决策，并说明你会怎么向团队解释 Big-O 与实际吞吐之间的关系。
- Python 的 `list.append` / C++ 的 `vector::push_back` 在容量不足时会申请更大的内存并搬移已有元素。以「容量满时容量翻倍」的策略为例： (1) 单次 append 的最坏时间复杂度是多少？ (2) 为什么文档和面试里普遍说 append 是 O(1)？请把 n 次连续 append 的总代价推出来。 (3) 如果把策略换成「每次容量不足时只加 1 个位置」，结论怎么变？ (4) 为什么工程实现里常见 ×2 或 ×1.5，而不是 ×1.1 或固定增量？
- 一个动态数组从容量 1 开始，每次写满就扩容为原来的 2 倍，并把旧元素全部拷贝到新数组。现在连续 append 100 万次（元素总数为 100 万）。请回答：(1) 整个过程总的元素拷贝次数是多少？(2) 单次 append 的最坏代价和均摊代价分别是多少？(3) 如果产品要求「任意单次操作的 P99 延迟抖动不能超过某个阈值」，这个 2 倍扩容策略有什么问题，你会怎么改？
- 你负责设计一个支持高并发写入的时序数据库内存索引。索引需要支持：写入新数据点（时间戳+值），以及按时间范围查询。团队提出用动态数组存储按时间排序的数据点，插入时如果数组满了就扩容为原来的 2 倍并拷贝。有人质疑：单次插入最坏 O(n) 拷贝，会拖高 P99 延迟，不能接受。你怎么用均摊分析评估这个设计？在 5 万 QPS 写入、SLA 要求 P99 < 10ms 的场景下，你会怎么决策？如果坚持要降低最坏延迟，有什么替代方案，复杂度如何变化？