文档介绍：计算机常用算法简介(1)
龚雄兴
2011年4月
主要内容
算法概述
分治与递归
动态规划
贪心算法
回溯法
分限界法
1、算法(Algorithm)
一、算法概述
2、程序(probram)
解决问题的方法(现实世界数字世界)。
算法的具体实现(具体的代码序列)
3、算法与程序的主要区别
算法的主要特征:
1)有输入:有零个或多个数据输入。
2)有输出:至少有一个数据输出。
3)确定性:组成算法的每个操作是无二义的。
4)有限性:每个操作的次数和时间是有限的。
程序可能不满足第4)条,如操作系统程序会重复地、无限地执行许多用户请求。
4、算法的评价标准
一、算法概述
1)正确性
2)直观性(可交流性)
3)容错性(健壮性)
4)分级性
5)高效性(时间,空间)*
5、与算法执行时间有关的主要因素
1)计算机速度
2)问题的规模
3)数据的原始状态。
4)算法的结构*
6、时间复杂性的评价方法
一、算法概述
1)最少次数-Tmin (n)
2)最坏次数-Tmax (n)
3)平均次数-Tavg(n)
4)渐近阶-T(n)
O(1) /O(n) / O(nlog2n) / O(n2)
7、算法的描述
自然语言
高级语言
伪代码
N-S图*
S1
S2
e
S1
S2
while/for……
S
一、算法概述
7、算法的描述
用N-S图描述的求一元二次方程的根的算法:
取得方程的参数:a,b,c
计算判别式:b2-4ac
判别式=0 ?
输出两相等实根
判别式>0 ?
输出两不等实根
输出两共扼虚根
一、算法概述
8、算法实例
顺序查找与二分查找
9、几个重要概念
1)数组与指针
2)函数与函数接口
3)传值与传址(传引用)
4)循环与递归
1、递归算法
二、分治策略
递归算法—直接或间接调用自己的算法。
递归算法的特点:
1)子问题结构相似,规模趋小
2)存在递归边界(递归结束条件)
如: 5!=5*4!
4!=4*3!
3!=3*2!
2!=2*1!
1!=1*0!
0!=1
int jc (int n)
{ if (n==0) return 1;
else return n*jc(n-1);
}
T(n)=1+T(n-1)
=1+1+T(n-2)
=……=n+T(0)
2、分治法的基本思想
二、分治策略
分治法的基本思想是将一个规模为n的问题分解为k个规模较少的子问题,这些子问题相互独立且与原问题结构相同。递归地求解这些子问题,然后将这些子问题的解合并得到原问题的解。
(n=n1+n2+……+nk)
3、分治法运用举例
1)求二叉树的叶结点数
int yz (BiNode *T)
{ if (!T) return 0;
else return
yz(T->lchild) + yz(T->rchild);
}
空树?
返回零
返回左,右子树叶子数之和
先序遍历:
中序遍历:
A
B
C
G
I
D
J
E
F
H
G
C
I
B
J
D
A
F
E
H
二、分治策略
3、分治法运用举例
2)已知二叉树T的先序和中序遍历序列分别为串l和r,试构造该二叉树T
ABCGIDJEFH
GCIBJDAFEH
某二叉树的先序遍历序列为ABCGIDJEFH,中序遍历序列为DCIBJDAFEH,构造该二叉树:
A
BCGIDJ
GCIBJD
EFH
FEH
B
E
CGI
GCI
F
F
H
H
DJ
JD
二、分治策略
3、分治法运用举例
2)已知二叉树T的先序和中序遍历序列分别为串l和r,试构造该二叉树T(续)