第 2 章 和式
# 和式
# 记号
艾弗森约定
为一个命题
提示
# 和式和递归式
- 和式和递归式互相转换的方法
快速排序
- 递推式的推导
为平均比较次数 的推导 - 对于快排的
partition
过程,需要次比较 - 然后判断左右两部分是否为
或 ,又需要 次比较 - 所以,对划分后的左右两部分进行递归前,一共需要
次比较 - 由于是随机排序的项目,所以左右两部分的大小也是随机的,设左右两部分大小分别为
, ,则 可能的取值有 ,共有 种可能,各种可能的比较次数相加,再除以 ,即可得平均比较次数为
- 对于快排的
调和数
# 和式的处理
三条运算定律
(2.15) ~ (2.17)
等差级数
- 借助交换律和分配律进行求解
- (2.18)
#
由艾弗森约定合并或分解项
- 作为扰动法的基础
几何级数
- (2.25)
采用微积分技巧来推导
- (2.26)
# 2.4 多重和式
🌟 重点
- 式 (2.27) 为交换求和次序的原理
- 式 (2.31) 是多重和式常用的公式
符号表示
交换求和次序的基本法则
- (2.16)
#
一般分配率 🌟
- (2.28)
交换求和次序的复杂形式
- 适用于内和的范围和外和的指标变量有关的情况
阵列的主对角线及其上方的所有元素之和
由二重和式推出切比雪夫不等式
- 二重和式
- 由艾弗森约定合并或分解项 化为 一般分配率 的形式
指标替换的一般形式及双射情况下的特例
一个具体的实例
- 推出调和级数的的累加式
# 一般性方法
# 有限微积分和无限微积分
🔲 待做事项
- 需要总结相关的公式
# 无限和式
🔲 待做事项
- 相关的定义需要动手总结
编辑 (opens new window)