算法设计与分析 课件 11-课程总结.pptx

;课程定位和作用;算法分析;一.算法分析;非形式定义：一个有穷的运算规则序列

运算规则确定了问题的解决方法

序列给出了解决方法的先后顺序

有穷性表现在：

运算规则序列是有穷的

对问题的合法输入，算法经有限

次运算后能终止并给出问题的解;确定性;正确性----算法设计的最低要求

工作量----算法在理论上需要的时间

空间量----算法在理论上需要的存储空间

简单性----算法可被理解程度

最优性----算法在同类算法中的水平;基石：计数法，即统计算法执行的基本操作次数。;步骤：1.确定基本操作；

2.分析有多少种输入；

3.分析每种输入执行的基本操作次数；

4.确定每种(类)输入出现的概率；

5.按相关公式建立关于n的表达式；

6.化简，得到相对简单的结果；

7.用渐近符号表示(得到最高阶项，忽略系数和低阶项）;算法的工作量通常有“平均时间复杂度（或平均性态）”和“最坏时间复杂度(或最坏性态)”两种表示。;?;?;步骤：

1.建立递推方程；

2.求解递推方程。

迭代法

递归树

主定理

……;递推方程：

一般形式为：;主定理;?;Ο(1)：常数级

Ο(logn)：对数级

Ο(n)：为线性级

Ο(nc)：多项式级

Ο(cn)：指数级

Ο(n!)：阶乘级;算法类－解决某一问题的各种算法中，用算法所执行的基本操作对算法进行划分，基本操作相同的算法为同类算法。;以最坏情况说明：;NP完全理论;易解问题与难解问题

P类问题

NP类问题

NPC类问题

NP难问题;二.算法设计;二.算法设计;divide-and-conquer(P){

if(|P|=n0)adhoc(P);//解决小规模的问题

//分解

dividePintosmallersubinstancesP1,P2,...,Pk；

//递归求解各子问题

for(i=1;i=k;i++)

yi=divide-and-conquer(Pi);

//将子问题的解合并为原问题的解

returnmerge(y1,...,yk);

};二.算法设计;二.算法设计;□动态规划;二.算法设计;二.算法设计;回溯法也称为通用解题法，是一种对问题解空间树进行深度优先的有哪些信誉好的足球投注网站算法，并在有哪些信誉好的足球投注网站过程中利用剪枝函数（约束函数和限界函数）提高有哪些信誉好的足球投注网站效率。;运用回溯法解题通常???含以下三个步骤：

针对所给问题，定义问题的解空间

确定易于有哪些信誉好的足球投注网站的解空间结构

以深度优先的方式有哪些信誉好的足球投注网站解空间，并且在有哪些信誉好的足球投注网站过程中用剪枝函数避免无效有哪些信誉好的足球投注网站;两类典型的解空间树：

子集树：当所给问题是从n个元素中找出满足某种性质的子集时，相应的解空间树称为子集树。

排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。;子集树算法框架;排列树算法框架;二.算法设计;二.算法设计;二.算法设计;确定算法：算法的每一计算步骤都是确定的，在输入不变的情况下，不管重复执行算法多少次，其结果都完全相同。;2.不同算法设计策略的联系与区别;学习内容;今后算法学习的内容