AlgoD&A_LectureNotes_W6

北航研究生算法设计讲义

Last Section

北航研究生算法设计讲义

Divide and Conquer 大整数乘法： n log 3 ≈ n1.59 矩阵乘法与STRASSEN 算法：nlog7 ≈ n2.81 最近点对：nlgn 凸包：nlgn,n2

北航研究生算法设计讲义

减治 插入排序: n2, n, n2/4 快速排序+插入排序 拓扑排序: 减一 生成排列+ Johnson-Trotter 生成子集+比特串方法

假币问题 俄式乘法 约瑟夫斯问题 欧几里德算法 插值查找 二叉查找树

北航研究生算法设计讲义

变治_实例化简 预排序– 检验数组中元素的惟一性： n(n-1)/2, nlogn+n – 模式计算： n(n-1)/2+n-1, nlogn+Θ(n)

高斯消去法– Partial pivoting – LU 分解 – 矩阵的逆

AVL树: 1.39logn, 1.01logn

北航研究生算法设计讲义

变治变换为同样实例的不同表现—改变表现 改变表现 (Representation Change) 2-3 树 堆和堆排序

北航研究生算法设计讲义

霍纳法则 问题： 针对一个给定的x 的多项式 p(x) = anxn + an-1xn-1 + … + a1x + a0 求值 霍纳法则是一个很好的改变表现技术的例子。 它不断地把x作为公因子从降次以后的剩余多项式 中提取出来： p(x) =(…(anx + an-1)x + ..)x + a0

北航研究生算法设计讲义

霍纳法则对于多项式 p(x) = 2x4 - x3 +3x2 + x - 5, 有： p(x) = 2x4 - x3 + 3x2 + x - 5 = x(2x3 - x2 + 3x + 1 )- 5 = x(x(2 x2 - x +3)+1)-5 = x(x(x(2 x-1)+3)+1)-5

北航研究生算法设计讲义

霍纳法则 用一个两行的表来帮助计算：– 第一行包含了该多项式的系数 – 第二行中，除了第一个单元用来存储an, 其他单元都 用来存储中间结果 – 用第二行的最后一个单元乘以x的值再加上第一行的下 一个系数， 来算出表格下一个单元的值 – 以这种方式算出的最后一个单元的值，就是该多项式 的值。 *例：计算 p(x) = 2x4 - x3 + 3x2 + x – 5 在x=3时的值

系数 2 -1 X=3 2 3*2+(-1)=5

3

1

-5 3*55-5=160

3*5+3=18 3*18+1=55

北航研究生算法设计讲义

霍纳法则Horner(P[0..n],x) //用霍纳法则求一个多项式在一个给定点的值 //输入：一个n次多项式的系数数组P[0..n](从低到高存储), 以及一个数字x //输出：多项式在x点的值 1. p←P[n] 2. for i←n-1 downto 0 do 3. p←x*p+P[i] 4. return p 乘法和加法次数均为 n

北航研究生算法设计讲义

二进制幂 霍纳法则计算an时，它退化成了一种对a 自 乘的蛮力算法，以及一些无用的加法。 两种基于改变表现思想的计算an 的算法：– 从左至右处理二进制串(n的二进制表示) – 从右至左处理

北航研究生算法设计讲义

二进制幂 设n = bI…bi…b0是在二进制系统中，表示一 个正整数n 的比特串，则可以通过以下多项 式的值来计算n: p(x) = bI xI + … + bi xi + … + b0 其中x = 2。 应用霍纳法则计算p(2) p←1 // n>=1, 第一个数字总是1 for i ← I-1 downto 0 do p ←2 p + bi

北航研究生算法设计讲义

二进制幂 a n = a p(2) : a p← a 1 for i ← I-1 downto 0 do a p ← a 2 p + bi 另

a

2 p + bi

=

a 2 p a bi

=

( a p ) 2 a bi

=

(a p ) 2

如果bi = 0 如果bi = 1

=

(a p ) 2 a

北航研究生算法设计讲义

二进制幂LeftRightBinaryExponentiation(a,b(n)) //用从左至右二进制幂算法计算an //输入

:一个数字a和二进制位bI,.., b0 的列表b(n), 这些位来自于一个正整数n的二进制展开式 //输出：an 的值 1. product ←a 2. for i←I-1 downto 0 do 3. product ←product*product 4. if bi = 1 then product ←product*a 5. return product

北航研究生算法设计讲义

二进制幂 因为该算法在每次重复它惟一循环的时候都要做 一到两次的乘法，所以它在计算an时，总的乘法 次数M(n)是 b-1 ≤ M(n) ≤2(b-1) b 是代表指数n 的比特串的长度 b-1 = log 2 n Vs. 减半

北航研究生算法设计讲义

问题化简(Reduction) P1 reduced to P2 which can be solved by Algo A Solve P2 with Algo A Solution of P2 transformed to P1

北航研究生算法设计讲义

问题化简_lcm Lcm(24,60)=120 24=2*2*2*3 质数因子 60=2*2*3*5 Lcm(24,60)=(2*2*3) *2*5 缺乏效率，并且需要一个连续质数的列表。 问题化简： lcm(m,n)和gcd(m,n)的积把m 和n 的每一个因子都 恰好包含了一次，因此就简单地等于m 和n 的积。 mn lcm(m,n) =

gcd(m, n)