二级公共基础知识.pptVIP

一、算法的基本概念

算法是解题方案的准确而完整的描述，它不等于程序，也不等计算方法。

1．算法的基本特征

可行性(effectiveness)

每一步要能实现

执行的结果达到预期的目的

确定性(definiteness)---非多义性

有穷性(finiteness)

拥有足够的情报----输入

;一、算法的基本概念

2．算法的基本要素

算法中对数据的运算和操作

算术运算

逻辑运算

关系运算

数据传输

算法的控制结构

顺序

选择

循环

;一、算法的基本概念

3．算法设计基本方法

列举法（工作量大找规律分类优化）

归纳法（列举少量找出一般关系可能是错的）

递推（也是归纳从初始条件逐次推出中间结果或最后结果）

递归（也是归纳从算法本身到达递归边界）

减半递推技术（分而治之规模减半重复减半）

回溯法（试探八皇后问题）

;一、算法的基本概念

算法的复杂度

1.时间复杂度

指执行算法所需要的计算工作量

算法工作量=f(n)n是问题的规模

与下列因素无关：

书写算法的程序设计语言

编译产生的机器语言，代码质量

机器执行指令的速度

;算法工作量的分析方法：

第一种情况：

在同一个问题规模下，算法执行所需的基本运算次数可能与输入有关（例如顺序查找），可以用两种方法分析算法工作量;(1)平均性态

当问题规模一定时，如果算法执行所需的基本运算次数取决于某一个特定的输入时，用此方法分析工作量

A(n)=

pi是某个元素(x)出现的概率,ti是在输入某个元素(x)时所执行的基本运算次数

;

(2)最坏情况复杂性

是指当问题规模为n时，算法所执行的基本运算的最大次数

W(n)=max(ti)

W(n)比A(n)更有实用价值;第二种情况：

算法的计算工作量也可能与输入无关（例如n阶矩阵相乘），在所有可能的输入下，算法所执行的基本运算次数是一定的，此时

A(n)=W(n)

;2.空间复杂度

是指执行这个算法所需要的内存空间

内存空间包括：

1）算法程序占用空间

2）输入的初始数据占用空间

3）算法执行中所需的额外空间

;二、数据结构的基本概念

数据结构研究三个问题:

(1)逻辑结构:??据集合中各元素之间所固有的逻辑关系

(2)存储结构:各数据元素在计算机中的存储关系

(3)运算:对各种数据结构进行运算

数据结构研究的目的:

(1)提高数据处理速度

(2)节省存储空间

;1.什么是数据结构

例如:无序表的顺序查找和有序表的对分查找

;35;(1)数据的逻辑结构

指数据元素的信息(即数据元素的集合,记为D)和各数据元素之间的前后件关系(记为R)。与它们在计算机中的存储位置无关.

记B为数据结构,则

B=(D,R);例如:一年四季的数据结构表示为:

B=(D,R)

D={春,夏,秋,冬}

R={(春,夏),(夏,秋),(秋,冬)}

用二元组表示数据元素之间的前后件关系

;(2)数据的存储结构(物理结构)

是指数据的逻辑结构在计算机存储空间中的存放形式

注意:各数据在计算机中的存储位置关系与它们的逻辑关系不一定是相同的.

一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有：

顺序

链接

索引

;2、数据结构的图形表示

例1:一年四季

春夏秋冬结点

例2:家庭成员

父亲

儿子女儿

;例3:用图形表示数据结构B=(D,R)

D={d1,d2,d3,d4,d5,d6,d7}

R={(d1,d3),(d1,d7),(d2,d4),(d3,d6),(d4,d5)}

d1d2

d3d7d4

d6d5

根结点(无前