算法设计与分析 Design and Analysis of Computer Algorithm
算法设计与分析 Design and Analysis of Computer Algorithm
算法设计与分析 第1章 算法概述 Algorithm Introduction 介绍算法设计的基本概念 及算法分析的方法和准则
算 法 概 述 Algorithm Introduction 第1章 介绍算法设计的基本概念 及算法分析的方法和准则 算法设计与分析
算法设计与分析 学习要点： 理解算法的概念。 理解什么是程序，程序与算法的区别和内在 联系。 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。 掌握用C++语言描述算法的方法
学习要点: 算法设计与分析 ❑ 理解算法的概念。 ❑ 理解什么是程序，程序与算法的区别和内在 联系。 ❑ 掌握算法的计算复杂性概念。 ❑ 掌握算法渐近复杂性的数学表述。 ❑ 掌握用C++语言描述算法的方法
算法设计与分析〉算法概述 1.1算法Algorithm 算法是什么？ 算法，一个既陌生又熟悉的名词。从小学就开始接触算 法。例如，做四则运算要先乘除后加减，从里往外脱括 弧等等都是算法，只要按照一定的程序一步一步做，一 定不会错。因此，算法其实是耳熟能详的数学对象。一 般地，算法是指在解决问题时按照某种机械程序步骤一 定可以得到结果的处理过程。这种过程必须是确定的、 有效的、有限的。 6
算法是什么？ 算法设计与分析 > 算法概述 1.1 算法 Algorithm 算法，一个既陌生又熟悉的名词。从小学就开始接触算 法。例如，做四则运算要先乘除后加减，从里往外脱括 弧等等都是算法，只要按照一定的程序一步一步做，一 定不会错。因此，算法其实是耳熟能详的数学对象。一 般地，算法是指在解决问题时按照某种机械程序步骤一 定可以得到结果的处理过程。这种过程必须是确定的、 有效的、有限的。 6
算法设计与分析〉算法概述 “如果你在森林里迷路了，保持冷静，调动常识，走一步 看一步。” 这里是建议而非算法。 童子军的条例： 如果你在森林里迷路了，一直往下走，直到溪流旁， 然后顺流而下，最后你会到达一个城镇。 这是一个算法。 7
算法设计与分析 > 算法概述 “如果你在森林里迷路了，保持冷静，调动常识，走一步 看一步。” ——这里是建议而非算法。 童子军的条例： 如果你在森林里迷路了，一直往下走，直到溪流旁， 然后顺流而下，最后你会到达一个城镇。 ——这是一个算法。 7
算法设计与分析>算法概述 1.算法定义 一系列将问题的输入转换为输出的计算或操作步骤 2.计算机算法与人工算法 有些问题没有计算机算法. 有些问题计算机算法与人工算法不同. 3.计算机算法的一般特征 (1)输入： 有外部提供的量作为算法的输入。 (2)输出： 算法产生至少一个量作为输出。 (3)确定性：definiteness 组成算法的每条指令是清晰，无歧义的。 (4)有限性：finiteness 算法中每条指令的执行次数是有限的，执行每条指令的时间也是有 限的。 8
8 一系列将问题的输入转换为输出的计算或操作步骤。 2. 计算机算法与人工算法 算法设计与分析 > 算法概述 1. 算法定义 有些问题没有计算机算法. 有些问题计算机算法与人工算法不同. (1)输 入： 有外部提供的量作为算法的输入。 (2)输 出： 算法产生至少一个量作为输出。 (3)确定性：definiteness 组成算法的每条指令是清晰，无歧义的。 (4)有限性：finiteness 算法中每条指令的执行次数是有限的，执行每条指令的时间也是有 限的。 3.计算机算法的一般特征
算法设计与分析〉算法概述 4.算法的三个要素 1)数据：运算序列中作为运算对象和结果的数据. 2)运算：运算序列中的各种运算：赋值，算术和逻辑运算 3)控制和转移：运算序列中的控制和转移. 5.算法描述语言 自然语言，数学语言，流程图，程序设计语言等等. 6.算法分类 从解法上 数值型算法：算法中的基本运算为算术运算 非数值型算法：算法中的基本运算为逻辑运算. 串行算法：串行计算机上执行的算法 从处理方式上 并行算法：并行计算机上执行的算法 9
9 算法设计与分析 > 算法概述 数值型算法:算法中的基本运算为算术运算. 非数值型算法:算法中的基本运算为逻辑运算. 串行算法:串行计算机上执行的算法. 并行算法:并行计算机上执行的算法. 从处理方式上 6. 算法分类 从解法上 5.算法描述语言 1).数据: 运算序列中作为运算对象和结果的数据. 2).运算: 运算序列中的各种运算:赋值,算术和逻辑运算 3).控制和转移: 运算序列中的控制和转移. 4.算法的三个要素 自然语言,数学语言,流程图,程序设计语言等等
算法设计与分析〉算法概述 7.问题的求解过程 理解问题 数学模型 2)建立数学模型 1)问题的陈述 通过对问题的分析， 用科学规范的语言， 找出其中的所有操 对所求解的问题做 作对象及操作对象 准确的描述. 之间的关系并用数 学语言加以描述， 3)设计算法 设计算法 根据数学模型设计问题的 4)算法的正确性证明 计算机求解算法 证明算法对一切合法 证明正确性 输入均能在有限次计 算后产生正确输出. 5)算法的程序实现 将算法正确地编写成机 设计程序 算法分析 器语言程序. 6)算法分析 对执行该算法所消耗的计算机资源进行估算. 10
10 算法设计与分析 > 算法概述 理解问题 设计程序 算法分析 证明正确性 数学模型 设计算法 1)问题的陈述 用科学规范的语言, 对所求解的问题做 准确的描述. 2)建立数学模型 通过对问题的分析, 找出其中的所有操 作对象及操作对象 之间的关系并用数 学语言加以描述. 3)设计算法 4)算法的正确性证明 5)算法的程序实现 6)算法分析 根据数学模型设计问题的 计算机求解算法. 证明算法对一切合法 输入均能在有限次计 算后产生正确输出. 对执行该算法所消耗的计算机资源进行估算. 将算法正确地编写成机 器语言程序. 7.问题的求解过程
算法设计与分析>算法概述 8.算法与程序、数据结构的关系 过程：算法+数据结构≈程序 对象：对象+消息≈程序 侧重点不同 数据的结构，直接影响算法的选择和效率。 算法—程序的灵魂 11
11 算法设计与分析 > 算法概述 8.算法与程序、数据结构的关系 过程：算法+数据结构程序 对象：对象+消息程序 侧重点不同 数据的结构，直接影响算法的选择和效率。 算法——程序的灵魂
算法设计与分析〉算法概述 8.算法与程序、数据结构的关系 线性表 数据结构的三个方面： 栈 线性结构 队列 串及数组 数据的逻辑结构 树形结构 非线性结构 图形结构 顺序存储 链式存储 数据的存储结构 索引存储 散列存储 数据的运算：检索、排序、插入、删除、修改等 12
12 数据的逻辑结构 数据的存储结构 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队列 树形结构 图形结构 数据结构的三个方面： 散列存储 索引存储 串及数组 数据的运算：检索、排序、插入、删除、修改等 算法设计与分析 > 算法概述 8.算法与程序、数据结构的关系