翻倍之后差了几倍
运行下面这段程序： def sq(n): return n * n print(sq(200) // sq(100))
阅读更多 →
数据量翻倍，O(n²) 会怎样
数据量翻一倍，一个 O(n²) 的算法耗时大约变成原来的【0】。
阅读更多 →
判断"能撑多大数据"要看什么
判断一个算法能不能撑住更大的数据，看的是【0】。
阅读更多 →
为什么小数据上 O(n²) 有时更快
数据量很小时，O(n²) 的做法有时反而比 O(n log n) 快，因为【0】。
阅读更多 →
换来的到底是多少
补全两个函数：brute_ops(n, m) 返回"每次都从头加一遍"做 m 次查询的操作数；prefix_ops(n, m) 返回"先建表再查"的操作数。 算
阅读更多 →
用前缀和查区间和
补全 range_sum：用前缀和求下标 l 到 r 的和。 ⚠️ l 是 0 的时候不能去取 p[-1]。 求下标 1 到 3 的和。
阅读更多 →
把前缀和表建出来
补全 build_prefix：返回一个列表，第 i 项是前 i+1 个数的总和。 建好之后把整张表拼起来输出（用 / 隔开）。
阅读更多 →
用它求中间三个数的和
同一张表，求下标 1 到 3 的和。运行下面这段程序： def build_prefix(a): p = [] s = 0 for x in a: s += x
阅读更多 →
前缀和表长什么样
运行下面这段程序： def build_prefix(a): p = [] s = 0 for x in a: s += x p.append(
阅读更多 →
前缀和的代价是什么
前缀和不是白拿的，它的代价是【0】。
阅读更多 →