《算法设计与分析》第一章：绪论
《算法设计与分析》第一章：绪论
算法设计与分析是计算机科学中的核心课程之一，它主要研究如何设计高效、正确的算法来解决各种计算问题。本文作为该课程的第一章内容，将介绍算法的基本概念、特性、描述方式、设计要求以及复杂度分析等基础知识，为后续章节的学习奠定基础。
算法概念
算法定义
算法定义：
算法是规则的有限集，是为解决特定问题而规定的一系列操作。
算法特性
五大特性：
- 有限性：有限步之后必须结束。
- 确定性：每一步骤必须有确切的含义，无二义。
- 可行性：原则上能精确地运行，即在现有条件情况下，是可以实现的。即使手工运算也能实现。
- 输入：有0个或多个输入，刻画运算对象的初始情况。
- 输出：有一个或多个输出，反映数据加工结果
�算法的描述方式
算法的描述方式：
- 自然语言：通俗易懂，容易掌握；但不够严谨、容易有二义性。
- 框图（流程图或N-S图）：重处理流程，便于检查修改；但无法表达数据流程。
- 高级语言：严谨、准确；细节过多。
- 伪代码（类语言）：结构性较强，比较容易书写和理解，修改起来也方便。
算法设计的要求
“好”算法标准（算法设计的要求）：
（1）正确
（2）可读性好
（3）健壮性高
（4）高效率低存储
算法设计与分析任务
设计阶段
该阶段的主要任务：对给定问题，如何设计解决此问题的有效算法。推而广之，对各类具体的问题设计高质量的算法，研究设计算法的一般规律和方法。
常用算法设计方法：
分治法、动态规划、贪婪法和回溯法等
分析阶段
研究算法质量判定准则。即对于设计出的每一个算法，讨论其时空复杂度，作为评价算法质量的标准之一，同时为算法改进提供参考。
算法设计与分析密切联系、相互影响：
- 设计的算法需要进行分析，评价其优劣；
- 评价结果可用于改进算法设计。
1.基本术语
2.证明方法
算法复杂度分析
时间复杂度
时间复杂度分析步骤：
（1）找算法中的基本语句（执行频率最高）；
（2）计算其执行次数，整理成问题规模n的函数；
（3）保留最高次幂，作为渐进时间复杂度。
空间复杂度
一个算法的存储量包括形参所占空间和临时变量所占空间。
在对算法进行存储空间分析时，
只考察临时变量所占空间
。
递归算法空间复杂度=每层需要的辅助空间*递归深度
最好，最坏和平均复杂度
例题：
采用顺序查找方法，在长度为n的一维整型数组a[0…n-1]中查找
值为x的元素。即从数组的第一个元素开始，逐个与被查值x进行比较。找到后返回1，否则返回0，对应的算法如下
渐近上界记号：O(big-oh)
大O符号：f(n)=O(g(n))，当且仅当存在正常量c和n0，使当n≥n0时，f(n)≤cg(n)，即g(n)为f(n)的上界。
例如：
大O符号用来描述增长率的上界，表示
f(n)的增长最 多像g(n) 增长的那样快
，表示算法消耗时间的上界。这
个
上界的阶越低，结果就越有价值
一个算法的时间用大O符号表示时，总是采用最有价
值的g(n)表示，称之为“紧凑上界”或“紧确上界”。
渐近下界记号：Ω(big-omega)
大Ω符号：f(n)= Ω(g(n))，当且仅当存在正常量c和n0，使当n≥n0时，f(n)≥cg(n)，即g(n)为f(n)的下界。
大Ω符号用来描述增长率的下界，表示
f(n)的增长最少像g(n) 增 长的那样快
，也就是说，当输入规模为n时，算法消耗时间的最小值。与大O符号对称，这个
下界的阶越高，结果就越有价值
一个算法的时间用大Ω符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑下界”或“紧确下界”。
渐近紧确界记号： Θ（big-theta）
大Θ符号：f(n)= Θ(g(n))，当且仅当存在正常量c1、c2
和n0，使当n≥n0时，有c1g(n)≤f(n)≤c2g(n)，即g(n)与f(n)
的同阶。
阶的证明
- 反证法
- 极限法
例题：