数据结构与算法 / 系统课时

求和与级数

求和与级数

算法分析经常需要把“循环执行了多少次”转换成一个求和式。本课从等差数列、等比数列和常见求和公式出发,建立从代码结构到执行次数的计算方法。

学习目标

  • 能够识别等差数列与等比数列,并选择正确的求和公式。
  • 能够把单层或嵌套循环的执行次数写成求和式。
  • 能够根据求和结果判断算法的时间复杂度。

核心原理

数列是按顺序排列的一组数,级数是这些数相加形成的表达式。算法分析关注的通常不是每一项本身,而是前 nn 项总量如何随 nn 增长。

等差数列

相邻两项之差固定为 dd 时,数列为等差数列。第 nn 项与前 nn 项和分别为:

an=a1+(n−1)da_n=a_1+(n-1)d
Sn=n(a1+an)2S_n=\frac{n(a_1+a_n)}{2}

最常见的情形是 1+2+⋯+n1+2+\cdots+n:

∑i=1ni=n(n+1)2\sum_{i=1}^{n} i=\frac{n(n+1)}{2}

该结果的最高次项是 12n2\frac{1}{2}n^2,因此当它计数常数成本的主要操作时,可得紧确阶 Θ(n2)\Theta(n^2)。

等比数列

等比数列满足 ai+1=qaia_{i+1}=q a_i。这样定义时,q=0q=0 或出现零项也能处理,无需求相邻项的比值。当 q≠1q\ne 1 时,前 nn 项和为:

Sn=a11−qn1−qS_n=a_1\frac{1-q^n}{1-q}

例如:

1+2+4+⋯+2m=2m+1−11+2+4+\cdots+2^m=2^{m+1}-1

等比级数常出现在分治算法、树的层级节点统计和容量倍增策略中。若 q=1q=1,所有项相等,不能套用分母为 1−q1-q 的公式,此时直接使用 Sn=na1S_n=na_1。

循环次数分析

分析循环时,先确定每次循环体执行多少次,再把各轮次数相加。下面的嵌套循环中,外层第 ii 轮会执行 ii 次内层操作:

python
count = 0
for i in range(1, n + 1):
    for _ in range(i):
        count += 1

总执行次数为:

T(n)=∑i=1ni=n(n+1)2T(n)=\sum_{i=1}^{n}i=\frac{n(n+1)}{2}

因此,精确次数是 n(n+1)2\frac{n(n+1)}{2},若循环体和计数操作均按常数成本计算,紧确时间阶为 Θ(n2)\Theta(n^2)。闭式公式只用常数次数的整数算术,逐项加和要 n 项。Python 整数位数可以随输入增长,不能把常数次算术等同于恒定实际耗时。约定 n=0 时为空和,结果是 0。

易错点

  • 把循环下标范围写错。例如 range(1, n + 1) 包含 11 到 nn,而 range(n) 包含 00 到 n−1n-1。
  • 只看嵌套层数就直接判断复杂度。内层次数可能是固定值、递减值或与外层变量有关,必须先写出求和式。
  • 在等比求和中忽略 q=1q=1 的边界,导致分母为零。

运行两种嵌套循环

第一种内层长度是 1、2、3 直到 n。第二种内层长度是 1、2、4,直到下一次倍增会超过 n。第二种总次数是 2m+1−12^{m+1}-1,其中 m=⌊log⁡2n⌋m=\lfloor\log_2 n\rfloor(n≥1),它至少为 n 且小于 2n。虽然两段都有嵌套,前者的计数为平方级,后者为线性级。n=0 时两者都为 0。

python
def triangle_count(n):
    if n < 0:
        raise ValueError("n 必须是非负整数")
    return sum(1 for i in range(1, n + 1) for _ in range(i))

def doubling_count(n):
    if n < 0:
        raise ValueError("n 必须是非负整数")
    width, count = 1, 0
    while width <= n:
        for _ in range(width):
            count += 1
        width *= 2
    return count

for n in (0, 5, 8):
    triangle = n * (n + 1) // 2
    doubling = (1 << n.bit_length()) - 1
    assert triangle_count(n) == triangle
    assert doubling_count(n) == doubling
    print(n, triangle, doubling)

三行结果依次为 (0, 0, 0)、(5, 15, 7)、(8, 36, 15)。这里统计的是内层操作次数,若每次操作本身变贵,整体成本要再乘或求和计入。

本课总结

  • 等差求和能够把逐轮递增的循环次数化为闭式公式。
  • 等比求和适合分析倍增、树层级和分治成本。
  • 判断复杂度时,应先得到总次数,再保留增长最快的项。

下一课预告

下一课将学习“指数与对数”,重点解释指数增长与对数互为逆运算,以及二分过程为什么会产生 O(log⁡n)O(\log n) 复杂度。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

求和与级数

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通