第01章算法的基本概念.pptVIP

* 2. 算法运行时间的评估 1）计算模型：RAM模型（随机存取机模型）、图灵机 模型等 2）初等操作：所有操作数都具有相同的固定字长；所 有操作的时间花费都是一个常数时间间隔。算术运 算；比较和逻辑运算；赋值运算，等等； * 例：百鸡问题算法的时间估计 可把 写成 第一个算法： 试计算第二个算法的时间估计？ * 3、算法时间复杂性的定义 定义：设算法的执行时间，如果存在 T’(n)，使得： 就称 T’(n) 为算法的渐近时间复杂性。 * 3、算法时间复杂性的定义 * 3、算法时间复杂性的定义 表1.2 不同时间复杂性下不同输入规模的运行时间 * 算法设计与分析 * Donald E.Knuth： 计算机科学就是 算法研究 * 在计算机科学与技术中的地位 操作系统、语言编译系统、数据库管理系统、以及各种各样的计算机应用系统软件，都用具体的算法来实现。 算法的好坏，决定了所实现软件性能的优劣。 在实现一个软件时，必须解决用什么方法设计算法、如何判定算法的性能。 * 目 录 第一章 算法的基本概念 第二章 算法的复杂性分析 第三章 排序问题与离散集合的操作 第四章 递归与分治 第五章 贪婪法 第六章 动态规划 第七章 回溯 第八章 分支与限界 第九章 随机算法 第十章 图和网络问题 第十一章 计算几何问题 第十二章 NP完全问题 第十三章 计算复杂性 第十四章 下界 第十五章 近似算法 * 1.1 引言 一 算法的定义和特征 二 算法设计的例子 三 算法的复杂性分析 * 1. 算法的定义 算法是解某一特定问题的一组有穷规则的集合 “Kitāb al-jabr Wa’lmuqābJla”（《复原和化简的规则》）→ Algebra（代数） Abū ‘Abd Allāh Muhammad ibn Mūsa al-Khwārizmī → Algorithm (算法) * 2. 算法的特征 1）有限性。算法在执行有限步之后必须终止。 2）确定性。算法的每一个步骤，都有精确的定义。要执行 的每一个动作都是清晰的、无歧义的。 3）输入。一个算法有0个或多个输入，它是由外部提供的， 作为算法开始执行前的初始值，或初始状态。算法的输入 是从特定的对象集合中抽取的。 4）输出。一个算法有一个或多个输出，这些输出，和输入有 特定的关系，实际上是输入的某种函数。不同取值的输 入，产生不同结果的输出。 5）能行性。算法的能行性指的是算法中有待实现的运算，都 是基本的运算。原则上可以由人们用纸和笔，在有限的时 间里精确地完成。 * 二 算法设计的例子 1. 穷举法 2. 百鸡问题 3. 货郎担问题 * 1. 穷举法 从有限集合中，逐一列举集合的所有元素，对每一个元素逐一判断和处理，从而找出问题的解 * 2. 百鸡问题 令 a：公鸡只数 b：母鸡只数 c：小鸡只数 约束方程： a + b + c = 100 5a + 3b + c/3 = 100 c % 3 = 0 a、b、c的可能取值范围：0 ~ 100 对在此范围内的a，b、c、的所有组合进行测试，凡是满足上述三个约束方程的组合，都是问题的解。 把问题转化为用 n 元钱买 n 只鸡，n 为任意正整数 约束方程： a + b + c = n 5a + 3b + c/3 = n c % 3 = 0 “鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。 百钱买百鸡，问鸡翁、母、雏各几何？” 方程求解？ 编程实现 * 1） 第一种解法： 输入：所购买的三种鸡的总数目n 输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g[ ],m[ ],s[ ] 1. void chicken_question(int n