循环不变式(Loop-Invariant)RAM模型(Random-Access Machine)算法时间复杂度的关注分支(Divide & Conquer)计算递归时间复杂度的方法替换法递归树主定理
循环不变式(Loop-Invariant)
- 证明排序算法的正确性
- 算法主体是循环
- 归纳证明:
- Initialization: 算法的初次迭代结果是正确的
- Maintenance:若上一次迭代的结果是正确的,则此次迭代结果仍是正确的
- Termination:当循环终止,该不变式可证明此算的正确性
RAM模型(Random-Access Machine)
基于RAM模型,算法在渐近分析框架下的计算时间,取决于算法执行过程中基本操作的执行次数。
算法时间复杂度的关注
- 时间消耗T(n)
- n→∞过程中,计算时间的增长率
- 渐进分析:关注最高次项
- 关注最坏情况
- 降低排序算法的开销:降低比较次数
分支(Divide & Conquer)
- 解决问题的一种通用方法
- 过程:
- 将大问题差分为子问题
- 攻克子问题(逻辑上递归)
- 结合解决子问题的子方法,解决大问题
- 举例:归并排序
计算递归时间复杂度的方法
替换法
- 猜测表达式
- 归纳证明
- 根据常数值求解
递归树
- 非正式,快速评估
- 假设每个子问题的规模都是相同的
主定理
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F240d44a8-41c7-4bfa-a212-0a2004eb958b%2FUntitled.png?table=block&id=727dec86-7c9a-410b-b290-dee782d7433f)
- 形式:
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F72de0472-c78a-4157-92aa-29226778f51a%2FUntitled.png?table=block&id=1fcdbcf1-18f9-473f-883e-55fa89ba9ed3)
- 三种情形:
- T(root)>T(leave)
- T(root)<T(leave)
- T(root)=T(leave)
- 总结
树根开销比叶子大
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F7aaa8b43-d00a-40d0-aa7b-b64daa953343%2FUntitled.png?table=block&id=f81044f2-e3fb-4126-af40-e0e754ac4fe9)
从树根到叶子,每层的开销等比递减
树根开销比叶子小
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F16bdc601-3bf2-49fe-9556-dde22c8b2ef2%2FUntitled.png?table=block&id=931d4feb-9346-4e0f-8c0d-7140258743c7)
树根和叶子的开销一样
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fcf02d5db-cfad-4a98-aa76-02a4ff484ea4%2FUntitled.png?table=block&id=0acbd71e-70ae-401b-acdf-c31fb5a1af7a)
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F6c7a8af8-b62d-4b61-9899-b30dd0f9c4d0%2FUntitled.png?table=block&id=a7923bb2-5716-4ef9-a5c3-b24e8fe582a0)