数据结构与算法
第一节 算法
一、 算法概念
算法：解题方案的准确而完整的描述。
（算法不等于程序）
1、算法基本特征：
1） 可行性：（算法与计算公式有差别）
2） 确定性：算法中的每一个步骤都必须有明确定义的，不允许有模棱两可的解释，也不允许有多义
性。
3） 有穷性：算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。
算法有穷性还应包括合理的执行时间的含义
4）拥有足够的情报
2、算法的基本要素：
两种基本要素：一是对数据对象的运算和操作，二是算法的控制结构。
1）算法中对数据的运算和操作(在计算机中)
算术运算：
逻辑运算：
关系运算：
数据传输：
算法的主要特征着重于算法的动态执行。
2）算法的控制结构
算法中各操作之间的执行顺序称为算法的控制结构。
描述算法的工具：传统流程图、N-S 结构化流程图、算法描述语言等。
一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。
4） 算法设计基本方法
列举法：
基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是
不需要的。常用于解决“是否存在”或“有多少种可能”等类型问题。
归纳法：
基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。
递推：
是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。本质上也属于归纳法。
递归：
在解决一些复杂问题时，为了降低问题的复杂程度，一般总是将问题逐层分解，最后归结为一些最简单的
问题。本质上也属于归纳法。
递归分为直接递归与间接递归两种。
减半递推技术（分治法）
所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”产过程。
回溯法
二、算法复杂度
算法的复杂度主要包括时间复杂度和空间复杂度。
1、时间复杂度
是指执行算法所需要的计算工作量。
算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即：
算法的工作量=f(n)
其中 n 是问题的规模。
在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法来
分析算法的工作量。
1） 平均性态：是指用各种特定输入下的运算次数的加权平均值来试题算法的工作量。
设 x 是所有可能输入中的某个特定输入，p(x)是 x 出现的概率，t(x)是算法在输入为 x 时所执行的基本运
算次数，则算法的平均性态定义为：
其中 D
n
表示当规模为 n 时，算法执行时所有可能输入的集合。
2）最坏情况复杂性
评论0
最新资源