两个主要任务 = 正确性(不变性 × 单调性)+ 复杂度
为确定后者,真地需要将算法描述为RAM的基本指令,再统计累计的执行次数?不必!
C++等高级语言的基本指令,均等效于常数条RAM的基本指令;在渐近意义下,二者大体相当
分支转向: goto // 算法的灵魂;出于结构化考虑,被隐藏了
迭代循环:for()、while()、… // 本质上就是 " if + goto"
调用 + 递归(自我调用)//本质上也是goto
复杂度分析的主要方法:
迭代:级数求和
递归:递归跟踪 + 递推方程
猜测 + 验证
级数:
实例:非极端元素+起泡排序
封底估算
减而治之
分而治之



