算法基础知识

一、算法的定义
算法：对特定问题求解步骤的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。
二、算法与程序的区别与联系
区别：
程序：与某种编程语言有关，能直接在机器上运行。
算法：与特定的语言无关，可用任何语言实现 ，甚至可以用自然语言实现。
联系：
程序=算法+数据结构
三、算法的基本特点
1）输入：有零个或多个输入。
2）输出：有一个或多个输出。
3）有穷性：在执行有穷步之后结束，且每一步都在有穷时间内完成。
4）确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。
5）可行性：算法描述的操作可以通过已经实现的基本操作执行有限次完成。
四、有效算法的五大特征：
1）正确性：能满足具体问题的需求，对于任何合法的输入，算法都会得出正确的结果；
2）健壮性：对非法输入的抵抗能力，即对于错误的输入，算法应能识别并做出相应处理，而不是产生错误结果或陷入瘫痪；
3）可读性：容易理解和实现。
4）时间效率高：运行时间短。
5）空间效率高：占用的存储空间尽量少。
五、算法的描述方法
1）自然语言
优点：容易理解
缺点：冗长、二义性
使用方法：粗线条描述算法思想
注意事项：避免写成自然段
2）程序流程图
优点：流程直观
缺点：缺少严密性、灵活性
使用方法：描述简单算法
注意事项：注意抽象层次
3）伪代码——算法语言
介于自然语言和程序设计语言之间，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言设计。
优点：表达能力强，抽象性强，容易理解
使用方法：自然语言+程序设计语言
4） 程序设计语言
优点：能由计算机执行
缺点：抽象性差，对语言要求高
使用方法：算法需要验证
注意事项：将算法写成子函数
六、算法设计的一般过程

七、重要问题类型
1.查找问题
2. 排序问题
3. 图问题
4. 组合问题
5. 几何问题
八、算法分析概述
1）什么是算法分析
分析算法占用的计算机资源的情况
2）算法分析的两个方面
时间复杂度——算法运行所需要的时间资源的量
空间复杂度——算法运行所需要的空间资源的量
3)算法分析的目的
设计算法——设计出复杂性尽可能低的算法
选择算法——在多种算法中选择复杂性最低的算法
九、时间复杂度分析
（1）时间复杂度分析

• 事后实验统计法——编写算法对应程序，统计其执行时间
• 事前分析估算法——渐近分析法
  通常采用渐进分析的方式来分析时间复杂度。

（2）渐近复杂度分析

（3）分析算法时间复杂度的一般步骤 ：

（4）渐进记号

1. 大〇符号——渐近上界记号
   
   一个算法的运行时间用大O符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑上界”或“紧确上界”。
   

2. 大Ω符号——渐近下界记号
   
   一个算法的运行时间用大符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑下界”或“紧确下界”。
   

总结：

（5）函数的阶

（6）最优算法

• 如果我们能够知道一个问题的计算复杂性下界，也就是求解该问题的任何算法（包括尚未发现的算法）所需的时间下界，即求解这个问题的最少工作量，就可以较准确地评价该问题的各种算法的效率，进而确定已有的算法还有多少改进的余地。

eg:

• 排序问题的复杂性的下界是Ω(nlogn)；
• 任何生成n个不同元素的所有排列对象的算法是Ω(n!)。

(7)算法的最好、最坏和平均情况

注意:
通常只求最坏情况运行时间，因为

• 给出了任何输入的运行时间的上界
• 对某些算法，最坏情况经常出现
• “平均情况”往往与最坏情况一样差

(8)渐近时间复杂度分析的一般步骤

1. 决定用哪个（或哪些）参数作为算法问题规模的度量
   可以从问题的描述中得到。
2. 找出算法中的基本语句
   通常是最内层循环的循环体。
3. 检查基本语句的执行次数是否只依赖于问题规模
   如果基本语句的执行次数还依赖于其他一些特性，则需要分别研究最好情况、最坏情况和平均情况的效率。
4. 建立基本语句执行次数的求和表达式
   计算基本语句执行的次数，建立一个代表算法运行时间的求和表达式。
5. 用渐进符号表示这个求和表达式
   计算基本语句执行次数的数量级，用大O符号来描述算法增长率的上限。

十、渐近空间复杂度分析
一个算法的存储量包括形参所占空间和临时变量所占空间。在对算法进行存储空间分析时，只考察临时变量所占空间。　

如果算法所需的辅助空间相对于问题的输入规模来说是一个常数，我们称此算法为原地（或就地）工作。
eg:

十一、递归算法复杂度分析的步骤

1. 建立递归方程
2. 求解该递归方程
3. 用渐近符号表示函数的阶

十二、递归方程的建立
递归方程：

• 递归方程是一个等式或不等式，它通过更小的输入上的函数值来描述一个函数。
• 当一个算法包含对其自身的递归调用时，可以用递归方程来表示其运行时间。

十三、递归方程的求解

1. 迭代法
   从初始递归方程开始，反复用递归方程右边的等式代入左边的函数，直到得到初值。
   

2. 代入法

• 猜测解的形式
• 用数学归纳法证明

3. 递归树法
   用树的形式给出一个递归算法执行的成本模型。
   （1）递归树法求解递归方程的步骤
   1）展开递归方程，构造对应的递归树
   2）将树中每层中的代价求和，得到每层代价，再将所有层的代价求和，得到总的递归调用代价
   （2）递归树的构造方法

• 递归树是一棵结点带权值的树，每个结点表示一个单一子问题的代价，子问题对应某次递归函数调用。
• 初始的递归树只有一个结点，它的权标记为T(n)；然后按照递归树的迭代规则不断进行迭代，每迭代一次递归树就增加一层，直到树中不再含有权值为函数的结点。

4. 主方法
   主方法适用于求解下面的递归形式：
   T(n)=aT(n/b)+f(n)
   其中a≥1，b>1为常数，f(n)为渐近正函数