这是 数学重学路线图 阶段三的子页面
求和公式与级数
为什么要学这个？
你以为”求和”就是小学数学？太天真了
分析嵌套循环复杂度 → 等差求和
理解指数退避重试策略 → 等比求和
估算分布式系统的累计耗时 → 级数
快速排序的期望比较次数 → 调和级数
暴力枚举不同密码长度的总尝试次数 → 等比求和
求和公式是”从具体到抽象”的桥梁，让你一眼看穿循环背后的数学规律
等差数列
定义：每一项与前一项之差恒定（公差 d）
通项公式：$a_n = a_1 + (n-1)d$
求和公式：
$S_n = \frac{n(a_1 + a_n)}{2}$
或者：$S_n = n \cdot a_1 + \frac{n(n-1)}{2} \cdot d$
直觉：首尾配对，每对之和相等
高斯求和故事
1 + 2 + 3 + … + 100 = ?
高斯（据说10岁时）：首尾配对
1 + 100 = 101
2 + 99 = 101
3 + 98 = 101
…共 50 对
答案 = 50 × 101 = 5050
用公式：S = 100 × (1 + 100) / 2 = 5050 ✓
等差数列常见变体
奇数求和：1 + 3 + 5 + … + (2n-1) = n²
证明：a₁=1, d=2, 共n项，S = n(1 + 2n-1)/2 = n²
偶数求和：2 + 4 + 6 + … + 2n = n(n+1)
连续整数平方和：1² + 2² + … + n² = n(n+1)(2n+1)/6
连续整数立方和：1³ + 2³ + … + n³ = [n(n+1)/2]²
等比数列
定义：每一项与前一项之比恒定（公比 r）
通项公式：$a_n = a_1 \times r^{n-1}$
求和公式（r ≠ 1）：$S_n = a_1 \cdot \frac{1 - r^n}{1 - r}$
直觉：等比数列增长极快（r > 1时）或衰减极快（|r| < 1时）
无穷等比级数
当 |r| < 1 时，等比级数收敛：
$S_{\infty} = \frac{a_1}{1 - r}$
例子：1 + 1/2 + 1/4 + 1/8 + … = 1/(1 - 1/2) = 2
直觉：你走到墙壁的一半，再走剩余距离的一半…永远走不到墙，总距离趋近2
等比数列的直觉速算
r = 2 时：1 + 2 + 4 + … + 2^(n-1) = 2^n - 1
这就是”翻倍增长的总和约等于最后一项的两倍”
例：1 + 2 + 4 + 8 + 16 = 31 ≈ 2 × 16
后端应用
嵌套循环复杂度分析
1
2
3
4
5
6
|
for i in range(n):
for j in range(i):
do_something()
|
很多 O(n²) 算法的精确操作次数就是 n(n-1)/2
冒泡排序、选择排序的比较次数都是这个
指数退避重试
请求失败后不要立即重试，等待时间指数增长：
第1次重试等 1s，第2次等 2s，第3次等 4s，第4次等 8s…
这是等比数列，公比 r = 2
重试 k 次的总等待时间 = 1 + 2 + 4 + … + 2^(k-1) = 2^k - 1 秒
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| import time
import random
def retry_with_exponential_backoff(func, max_retries=5, base_delay=1.0):
"""指数退避重试策略"""
for attempt in range(max_retries):
try:
return func()
except Exception as e:
if attempt == max_retries - 1:
raise
delay = base_delay * (2 ** attempt)
jitter = random.uniform(0, delay * 0.1)
total_delay = delay + jitter
print(f"第{attempt+1}次重试，等待 {total_delay:.2f}s")
time.sleep(total_delay)
|
缓存过期时间抖动
如果所有缓存同时过期 → 缓存雪崩
解决：基础过期时间 + 随机抖动
抖动范围通常是基础时间的 10%-20%
大数据应用
分片大小估算
总数据 10TB，分成 n 片处理
每片处理时间与片大小成正比：t(片) ∝ 10TB/n
总时间 = n × (固定开销 + 处理时间) = n × c + 10TB × k / n
这是一个先减后增的函数，存在最优分片数
批量处理的累计耗时
每批处理 1000 条，但随着数据增长，每批变慢
如果第 k 批耗时 = k × t₀（线性增长），总耗时 = t₀ × (1+2+…+n) = t₀ × n(n+1)/2
等差求和告诉你：看起来线性增长的单批耗时，累计起来是二次增长！
安全应用
暴力枚举不同密码长度的总尝试次数
字符集大小 k = 62（大小写+数字）
1位密码：62 种
2位密码：62² 种
…
n位密码：62^n 种
尝试所有 1 到 n 位的密码：总数 = 62 + 62² + … + 62^n
等比求和：S = 62 × (62^n - 1) / (62 - 1)
关键洞察：总数 ≈ 62^n × (62/61) ≈ 最长密码的尝试次数
即：攻击者几乎所有时间都花在尝试最长的那一位上
暴力破解时间估算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| def estimate_brute_force(charset_size, max_length, attempts_per_second):
"""估算暴力破解所有1到max_length位密码的时间"""
total = 0
for length in range(1, max_length + 1):
combinations = charset_size ** length
total += combinations
formula_total = charset_size * (charset_size**max_length - 1) / (charset_size - 1)
seconds = total / attempts_per_second
print(f"字符集大小: {charset_size}")
print(f"最大长度: {max_length}")
print(f"总组合数: {total:,.0f}")
print(f"公式验证: {formula_total:,.0f}")
print(f"每秒尝试: {attempts_per_second:,}")
if seconds < 60:
print(f"预计时间: {seconds:.1f} 秒")
elif seconds < 3600:
print(f"预计时间: {seconds/60:.1f} 分钟")
elif seconds < 86400:
print(f"预计时间: {seconds/3600:.1f} 小时")
elif seconds < 365.25*86400:
print(f"预计时间: {seconds/86400:.1f} 天")
else:
print(f"预计时间: {seconds/(365.25*86400):.1f} 年")
estimate_brute_force(62, 8, 10_000_000_000)
print("---")
estimate_brute_force(62, 8, 100)
|
调和级数
定义：$H_n = 1 + \frac{1}{2} + \frac{1}{3} + … + \frac{1}{n}$
近似：$H_n \approx \ln(n) + \gamma$，其中 $\gamma \approx 0.5772$（欧拉-马斯切罗尼常数）
特点：调和级数发散（趋向无穷），但增长极慢
直觉：增长速度和 ln(n) 差不多，比任何正幂次都慢
和算法分析的关系
快速排序期望比较次数：≈ 2n × Hₙ ≈ 2n ln n ≈ 1.39 n log₂ n
优惠券收集问题：集齐 n 种卡片的期望购买次数 = n × Hₙ ≈ n ln n
例：集齐12生肖邮票期望买 12 × H₁₂ ≈ 12 × 3.1 ≈ 37 张
随机化算法分析中频繁出现
Python 代码：验证求和公式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| import math
def arithmetic_sum_loop(a1, d, n):
"""循环求和"""
return sum(a1 + i * d for i in range(n))
def arithmetic_sum_formula(a1, d, n):
"""公式求和"""
return n * a1 + n * (n - 1) * d // 2
print("1+2+...+100 =", arithmetic_sum_loop(1, 1, 100))
print("公式结果 =", arithmetic_sum_formula(1, 1, 100))
print("高斯公式 =", 100 * 101 // 2)
print()
def geometric_sum_loop(a1, r, n):
"""循环求和"""
return sum(a1 * r**i for i in range(n))
def geometric_sum_formula(a1, r, n):
"""公式求和"""
if r == 1:
return a1 * n
return a1 * (1 - r**n) / (1 - r)
print("1+2+4+...+512 =", geometric_sum_loop(1, 2, 10))
print("公式结果 =", geometric_sum_formula(1, 2, 10))
print("2^10 - 1 =", 2**10 - 1)
print()
def infinite_geometric_partial(a1, r, n_terms):
"""前n项和，观察收敛"""
partial = 0
for i in range(n_terms):
partial += a1 * r**i
return partial
print("无穷等比级数 a1=1, r=0.5 收敛过程：")
for n in [5, 10, 20, 50]:
s = infinite_geometric_partial(1, 0.5, n)
print(f" 前{n:>2}项和 = {s:.10f} (理论极限 = 2.0)")
print()
def harmonic_number(n):
return sum(1/k for k in range(1, n+1))
print("调和级数 vs ln(n) + γ：")
gamma = 0.5772156649
for n in [10, 100, 1000, 10000, 100000]:
hn = harmonic_number(n)
approx = math.log(n) + gamma
print(f" H({n:>6}) = {hn:.6f}, ln({n})+γ = {approx:.6f}, 误差 = {abs(hn-approx):.6f}")
|
Python 代码：模拟指数退避
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| import random
def simulate_exponential_backoff(success_prob=0.3, max_retries=8, base_delay=1.0):
"""模拟指数退避重试"""
total_wait = 0
for attempt in range(max_retries):
if random.random() < success_prob:
print(f"第{attempt+1}次尝试成功！总等待时间: {total_wait:.2f}s")
return True, total_wait
delay = base_delay * (2 ** attempt)
jitter = random.uniform(0, delay * 0.1)
wait = delay + jitter
total_wait += wait
print(f"第{attempt+1}次失败，等待 {wait:.2f}s (累计 {total_wait:.2f}s)")
print(f"全部{max_retries}次重试失败，总等待: {total_wait:.2f}s")
return False, total_wait
random.seed(42)
simulate_exponential_backoff()
print("\n--- 理论最大等待时间 ---")
for max_r in range(1, 9):
total = sum(2**i for i in range(max_r))
print(f"最多重试{max_r}次: 最大等待 = {total}s = {total/60:.1f}min")
|
Python 代码：级数收敛/发散可视化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| import matplotlib.pyplot as plt
import numpy as np
n_terms = 50
x = np.arange(1, n_terms + 1)
geometric_partial = np.cumsum(0.5 ** np.arange(n_terms))
harmonic_partial = np.cumsum(1.0 / x)
p2_partial = np.cumsum(1.0 / x**2)
fig, axes = plt.subplots(1, 3, figsize=(18, 5))
axes[0].plot(x, geometric_partial, 'b-', linewidth=2)
axes[0].axhline(y=2.0, color='r', linestyle='--', label='极限 = 2')
axes[0].set_title('等比级数 (r=0.5) - 收敛到 2')
axes[0].set_xlabel('项数')
axes[0].set_ylabel('部分和')
axes[0].legend()
axes[0].grid(True, alpha=0.3)
axes[1].plot(x, harmonic_partial, 'g-', linewidth=2)
axes[1].plot(x, np.log(x) + 0.5772, 'r--', linewidth=1, label='ln(n) + γ')
axes[1].set_title('调和级数 - 发散（慢慢趋向无穷）')
axes[1].set_xlabel('项数')
axes[1].set_ylabel('部分和')
axes[1].legend()
axes[1].grid(True, alpha=0.3)
axes[2].plot(x, p2_partial, 'm-', linewidth=2)
axes[2].axhline(y=np.pi**2/6, color='r', linestyle='--', label=f'极限 = π²/6 ≈ {np.pi**2/6:.4f}')
axes[2].set_title('p=2 级数 - 收敛到 π²/6')
axes[2].set_xlabel('项数')
axes[2].set_ylabel('部分和')
axes[2].legend()
axes[2].grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('series_convergence.png', dpi=150)
plt.show()
|
常见误区
误区1：等比求和只在数学题里出现
指数退避、分治递归的时间分析、缓存层级延迟，全是等比
误区2：调和级数收敛
不！调和级数发散，只是发散得极慢
但 p > 1 的级数（如 1/n²）收敛
误区3：n(n-1)/2 和 n² 差很多
n(n-1)/2 = n²/2 - n/2，大O意义下就是 O(n²)
但精确计算时差一倍，实际工程中这个常数可能很重要
误区4：无穷级数的和等于”加了无穷多次”
数学上是极限的概念，不是真的加了无穷次
发散级数的”和”没有意义（如 1+2+3+…=”=-1/12” 是解析延拓，不是普通求和）
练习题
练习1：一个API使用指数退避策略，基础等待1s，公比2，最多重试10次。如果全部失败，总等待时间是多少？
答案：S = 1 + 2 + 4 + … + 2^9 = 2^10 - 1 = 1023 秒 ≈ 17 分钟
练习2：分析这段代码的精确执行次数和大O复杂度
1
2
3
4
| count = 0
for i in range(n):
for j in range(i, n):
count += 1
|
答案：j 的循环次数分别是 n, n-1, n-2, …, 1。总次数 = n + (n-1) + … + 1 = n(n+1)/2。大O = O(n²)。
练习3：某垃圾邮件发送者每天发送量翻倍（第1天发1000封，第2天2000封…）。7天内总共发了多少封？如果要追踪”至少发了100万封”的时间点呢？
答案：7天总量 = 1000 × (2^7 - 1) = 1000 × 127 = 127,000 封。累计达100万：1000 × (2^n - 1) ≥ 1,000,000 → 2^n ≥ 1001 → n ≥ 10（第10天累计约102.3万封）。
练习4：优惠券收集问题——系统有20种不同的随机奖励，期望收集多少次才能集齐？
答案：期望次数 = 20 × H₂₀ = 20 × (1 + 1/2 + 1/3 + … + 1/20) ≈ 20 × 3.5977 ≈ 71.95 次。
练习5：证明 1 + 1/2 + 1/4 + 1/8 + … = 2
答案：这是首项 a₁=1、公比 r=1/2 的无穷等比级数。|r|=1/2 < 1，收敛。S = a₁/(1-r) = 1/(1-1/2) = 1/(1/2) = 2。