数据结构与算法学习笔记 5 （2018.10.08）

算法分析

• 两个主要任务 = 正确性（不变性 × 单调性 ） + 复杂度
• 为确定后者，真地需要将算法描述为RAM的基本指令，再统计累计的执行次数？不需要！
• C++等高级语言的基本指令，均等效于常数条RAM的基本指令；在渐进意义下，二者大体相当

                             分支转向：goto            //算法的灵魂；处于结构化考虑，被隐藏了

                             迭代循环： for（），while（），... //本质上就是 “if + goto”

                             调用 + 递归 （自我调用） //本质上也是goto

• 复杂度分析的主要方法

                             迭代：级数求和

                             递归：递归跟踪 + 递推方程

                             猜测 + 验证

级数

循环 Vs 级数

取非极端元素