经开区工厂储备班线长开学典礼.ppt

算法设计与分析
徐义春
Hi./chinaxuyichun
1
关于本课程
课程目的:计算机算法设计与分析导引
以算法设计为主,介绍算法设计的主要方法和基本思想;并简要介绍算法分析概念
不是程序设计课,也不是数学课
授课形式:上课+作业+期末考试
教材:《计算机算法分析与设计》王晓东
电子文献:山东师范大学徐连诚ppt
2
第1章算法概述
本章主要知识点:
算法与程序
算法与数据结构
描述算法与算法设计
算法分析的基本原则
算法复杂性分析
3
算法与程序
算法:是满足下述性质的指令序列。
输入:有零个或多个外部量作为算法的输入。
输出:算法产生至少一个量作为输出。
确定性:组成算法的每条指令清晰、无歧义。
有限性:算法中每条指令的执行次数有限,执行每条指令的时间也有限。
程序:
程序是算法用某种程序设计语言的具体实现。
4
算法与数据结构
描述算法可以有多种方式
自然语言方式、表格方式、图示形式等
教材采用C++与自然语言相结合的方式
算法与数据结构的关系
不了解施加于数据上的算法就无法决定如何构造数据,可以说算法是数据结构的灵魂;
反之算法的结构和选择又常常在很大程度上依赖于数据结构,数据结构则是算法的基础。
算法+数据结构=程序
5
描述算法与算法设计
描述算法可以有多种方式,如自然语言方式、图形表格方式等。在这里,我们将采用C++语言来描述算法。
C++语言的优点是类型丰富、语句精炼,具有面向对象和面向过程的双重优点。
用C++来描述算法可使整个算法结构紧凑、可读性强。
在课程中,有时为了更好地阐明算法的思路,我们还采用C++与自然语言相结合的方式来描述算法。
算法设计方法主要有:分治策略、动态规划、贪心算法、回溯法、分支限界、概率算法等,我们将在后面的章节中陆续介绍。
6
描述算法与算法设计
问题求解(Problem Solving)
证明正确性
分析算法
设计程序
理解问题
精确解或近似解
选择数据结构
算法设计策略
设计算法
7
算法分析的基本原则
正确性
定义:在给定有效输入后,算法经过有限时间的计算并产生正确的答案,就称算法是正确的。
正确性证明的内容:
方法的正确性证明——算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。
程序的正确性证明——证明所给出的一系列指令确实做了所要求的工作。
程序正确性证明的方法:
大型程序的正确性证明——可以将它分解为小的相互独立的互不相交的模块,分别验证。
小模块程序可以使用以下方法验证:数学归纳法、软件形式方法等。
8
算法分析的基本原则
工作量——时间复杂性分析
计量工作量的标准: 对于给定问题,该算法所执行的基本运算的次数。
基本运算的选择:根据问题选择适当的基本运算。
问题
基本运算
在表中查找x
比较
实矩阵相乘
实数乘法
排序
比较
遍历二叉树
置指针
9
算法分析的基本原则
占用空间——空间复杂性分析
两种占用:
存储程序和输入数据的空间
存储中间结果或操作单元所占用空间——额外空间
影响空间的主要因素:
存储程序的空间一般是常数(和输入规模无关)
输入数据空间为输入规模O(n)
空间复杂性考虑的是额外空间的大小
如果额外空间相对于输入规模是常数,称为原地工作的算法。
10