刷题
刷题
learn
learn
日期
Aug 29, 2024
- 从思想上理解递归：画调用图是非常重要的，有利于分析递归；
- 从实际上理解递归：递归不是玄学，底层是利用系统栈来实现的；
- 任何递归函数都一定可以改成非递归，不用系统帮你压栈（系统栈空间），自己压栈（内存空间）
- 递归改成非递归的必要性：
- 工程上几乎一定要改，除非数据量再大递归也一定不深，如：归并排序、快速排序、线段树、很多的平衡树等
- 算法鄙视或者比赛中（能通过就不改）
- master公式：
- 所有子问题规模相同的递归才能用master公式：，、、都是常数
- 如果，复杂度为
- 如果，复杂度为
- 如果，复杂度为
- 一个补充：，时间复杂度是