算法分析笔记----wsdchong

时间：2018/12/20

一、算法概述

什么是算法

1.算法：为一个计算的具体步骤；常用于计算、数据处理、推理等

性质：有限、确定、可行、输入、输出；

目的：解决问题（问题定义了输入和输出）

2.例子：割圆术、四则运算、快速排列、最小生成树、求最大公因子算法；

算法的位置

1计算机体系：

可计算否—>能行可计算否—>算法设计与分析—>计算机语言实现—>软件系统

2可计算理论：计算模型、可计算问题、计算模型的等价性

3.计算复杂性理论：

算法分析引论

1.正确性：程序调试只能证明有错，而程序的正确性需要归纳证明

2.复杂性分析：

目的：预测算法对不同输入所需资源量；

复杂性测度：时间（步数）、空间、I/O等，是输入大小的函数；

用途：为求解一个问题选择最佳算法；

需要的数学基础：离散数学、组合数学、概率论、代数等

需要的数学能力：建立数学模型、化简数学模型

3. 时间复杂性（步骤数）

算法设计引论

1.算法设计模式：暴力搜索、分治法、图搜索与枚举、随机化方法；

2.算法实现方法：递归与迭代、串行与并行、确定性与非确定性、近似求解与精确求解；

3.最优化算法设计方法：线性规划、动态规划、贪心法、启发式方法

二、算法分析的数学基础

计算复杂性函数的阶

1.增长的阶：描述增长率

2.增长函数：典型的增长阶（1，n，n!，lg n）

3.增长的记号：同阶函数集合、低阶函数集合、高阶函数集合、严格低阶函数、严格高阶函数集合

4.渐进符号的性质：传递性、自反性、对称性、反对称性

和式的估计与界限

1.线性和

2.级数

3.和的界限：直接求和的界限

递归方程

1.概念：使用小的输入值来描述一个函数的方程或不等式；

2.求解递归方程的方法：替换方法、迭代方法、master定理方法

3.替换方法：提出猜想（上下界猜测），用数学归纳法证明

4.迭代方法：将方程转化为和式，用估计和的方法求解、

三、分治算法

分治法

1.设计过程：划分、求解、合并（自顶向下）

实例

1.大整数乘法：划分

算法分析：建立递归方程、使用master定理得出T(n)=O(n)

2.最大值和最小值：归并排序

元素提取问题的线性时间算法

1.中位数问题定义：比较操作次数的上下界

2.线性时间选择：分组、排序、递归调用算法、MOM划分、递归

快速傅里叶变换

四、动态规划

基本原理

1.子问题重叠：自底向上的计算

2.优化子结构、重叠子问题

矩阵乘法问题

最长公共子序列问题

五、贪吃算法

贪心法的基本原理

1.每一步只有一组选择；每次做出当前最好的选择；（希望通过局部优化选择达到全局优化选择）

任务安排问题

哈夫曼编码问题

六、搜索策略