算法设计与分析复习讲义.doc

课程介绍
干晓聪 sliant13@ ********** 南海楼308
sina微博资料下载通知
1~16周教学 17~18周复****答疑 19~20考试周
考试卷面 60% 考平时所讲知识点不考编程考前有复****题库
平时成绩 40% 作业=上机实验自选题目交十次,或大作业(需同意)
上机:南海楼209 每周四下午 14:00~16:00 Java 16:00~18:00数据结构
交作业,可在宿舍做
上课出勤
课程定位:计算机基础=> 编程语言=> 数据结构=> 算法=> 复杂性理论,专题方向
横向扩充,纵向深入
教材参考书做题学****方法:编程基础是前提,自学最重要
收集:面试题,算法题,编程题,智力题
引论
一些数学公式
估计调和级数前n项 1/x积分得对数 1/x和1/(x+1)所夹估计误差前若干项精确计算,后面误差小

i数的通项:母函数,z变换
计算机中的数
进制转换:Dec Bin Hex Oct
整数转换:Dec Int => Bin模二任意进制
带权相加:Bin Int/Float => Dec 任意进制
浮点数除法:4/3转二进制任意进制
二进制的乘除法 x*3
整数编码:补码
浮点数编码:IEEE 754,二进制科学计数法,能表示的浮点数个数是有限的,能表示的浮点数的精度是有限的,浮点数在数轴上的分布是不均匀的。
HEX 16进制编码
有效数字
指数
实际表示
名称
说明
符号+指数
纯小数
000
0000000000000
0
线性区
0000000000001
2-1022*2-52
subnormal min
FFFFFFFFFFFFF
2-1022 *(1-2-52)
subnormal max
001
0000000000000
1+0
-1022
2-1022
realmin
3CB
0000000000000
1+0
-52
2-52
eps
精度,HEX
3FF
0000000000000
1+0
0
1
3FF
FFFFFFFFFFFFF
2-eps
0
2-eps
...
400
0000000000000
1+0
1
2
屏幕显示2
400
8000000000000
1+1/2
1
3
7FE
FFFFFFFFFFFFF
2-eps
1023
(2-eps)*21023
realmax
7FF
0000000000000
inf
x/0
7FF
xxxxxxxxxxxxx
NaN
0/0; 一般FFF 8000000000000
考虑-0,-inf
Matlab演示 format long format hex format short format
1 / 0 = inf
0 / 0 = NaN
运算时阶码调整/对齐 1/2 4+1
1+eps = HEX 3FF 0000000000001
2+eps = HEX 400 0000000000000
浮点数的误差:x=1+eps, x-1 x=2+eps, x-2
x=4/3-1, y=3*x, z=1-y
程序中的数据
数组:下标
指针:地址;内存看作巨大的字节数组,下标
结构;首地址+偏移=实际地址
本质上都是地址/指针
内存,磁盘:巨大数组段页式/扇区、簇、文件分配碎片
算法分析
时间复杂度
1
for ( int i = 0; i < n; i ++ )
for ( int j = 0; j < (int) ( n ); j ++ )
foo();
P11
P12法则3
有一个时间复杂度为n^2的程序,当n=10^3时运行了1s,当n=10^6时要运行多长时间?
题
数组顺序查找:n
数组二分查找:ln(n)
数组翻转
两/三个有序数组合并
矩阵存储
矩阵的一维数组存储n^2、打印
三角阵的一维数组存储n^2/2 打印
对称阵
Toeplitz阵
最大定长子序列和:求积分
最大子序列和,不定长:n^3, n^2
求积分,转为求最大增长式落差。注意最大子序列,起点一定是终点前的最小值,终点一定是起点后的最大值。从前往后扫描积分序列,求以当前点为终点的最大增长落差:记录迄今为止最小值,与当前值之差就是。
再参见P21算法4,里面的ThisSum就是以当前点为终点的最大子序列,其清零对应在积分序列里,每次碰到迄今最小值