数据结构与算法 / 系统课时
求和与级数
求和与级数
算法分析经常需要把“循环执行了多少次”转换成一个求和式。本课从等差数列、等比数列和常见求和公式出发,建立从代码结构到执行次数的计算方法。
学习目标
- 能够识别等差数列与等比数列,并选择正确的求和公式。
- 能够把单层或嵌套循环的执行次数写成求和式。
- 能够根据求和结果判断算法的时间复杂度。
核心原理
数列是按顺序排列的一组数,级数是这些数相加形成的表达式。算法分析关注的通常不是每一项本身,而是前 项总量如何随 增长。
等差数列
相邻两项之差固定为 时,数列为等差数列。第 项与前 项和分别为:
最常见的情形是 :
该结果的最高次项是 ,因此当它计数常数成本的主要操作时,可得紧确阶 。
等比数列
等比数列满足 。这样定义时, 或出现零项也能处理,无需求相邻项的比值。当 时,前 项和为:
例如:
等比级数常出现在分治算法、树的层级节点统计和容量倍增策略中。若 ,所有项相等,不能套用分母为 的公式,此时直接使用 。
循环次数分析
分析循环时,先确定每次循环体执行多少次,再把各轮次数相加。下面的嵌套循环中,外层第 轮会执行 次内层操作:
count = 0
for i in range(1, n + 1):
for _ in range(i):
count += 1总执行次数为:
因此,精确次数是 ,若循环体和计数操作均按常数成本计算,紧确时间阶为 。闭式公式只用常数次数的整数算术,逐项加和要 n 项。Python 整数位数可以随输入增长,不能把常数次算术等同于恒定实际耗时。约定 n=0 时为空和,结果是 0。
易错点
- 把循环下标范围写错。例如
range(1, n + 1)包含 到 ,而range(n)包含 到 。 - 只看嵌套层数就直接判断复杂度。内层次数可能是固定值、递减值或与外层变量有关,必须先写出求和式。
- 在等比求和中忽略 的边界,导致分母为零。
运行两种嵌套循环
第一种内层长度是 1、2、3 直到 n。第二种内层长度是 1、2、4,直到下一次倍增会超过 n。第二种总次数是 ,其中 (n≥1),它至少为 n 且小于 2n。虽然两段都有嵌套,前者的计数为平方级,后者为线性级。n=0 时两者都为 0。
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)。这里统计的是内层操作次数,若每次操作本身变贵,整体成本要再乘或求和计入。
本课总结
- 等差求和能够把逐轮递增的循环次数化为闭式公式。
- 等比求和适合分析倍增、树层级和分治成本。
- 判断复杂度时,应先得到总次数,再保留增长最快的项。
下一课预告
下一课将学习“指数与对数”,重点解释指数增长与对数互为逆运算,以及二分过程为什么会产生 复杂度。