算法设计与分析>算法概述 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.算法与程序、数据结构的关系