算法与计算复杂性课程(8)算法分析.pdf

顺序算法分析的基本方法 算法分析的原则 正确性工作量占用空间 简单性最优性问题复杂度 算法分析的实例 搜索有序表 排序 选择 1 算法分析的原则 正确性 概念在给定有效输入后, 算法经过有限时间的计 算并产生正确的答案, 就称算法是正确的. 正确性证明的内容 方法的正确性证明算法思路的正确性. 证明一系列与算法的工作对象有关的引理定 理以及公式. 程序的正确性证明证明所给出的一系列指令 确实做了