THU

THU"/>

THU

数据结构，邓俊辉老师
平台——学堂在线 =learn_title

动态规划

动态规划的引入

Make it work, Make it right, Make it fast.
Kent Beck

通过递归给到一个初步的解后，再进行改进

首先，观察实例——斐波那契数列的递归计算
+现象，在43项后结果产生发生延迟，查看任务管理器，发现内存满负荷工作
+问题 代码这么慢，从复杂度的角度到底如何解释？
O(φ^n)，斐波那契的递归实例，在时间复杂度上呈指数级别

封底估算

• φ = 黄金分割比例（长/短）约为1.61803

• φ^36 = 2^25

• φ^43 = 2^30 = 10^9 flo = 1sec
  即，普通计算机一秒钟的吞吐量
  更好理解指数，有助于对我们估计计算的延迟

• 近似式φ^5大致是10，
  那么φ^67次方大致是10^14 flo= 10^5 sec = 1 day

用递归跟踪方法，认识到递归版fib()低效的根源在于，各递归实例均被大量重复调用
改进思维：每个实例只计算一次，改进算法

斐波那契数列的迭代法

改进方法一，是直截了当的（记忆法：memoization）
每次试图生成新的递归实例时，都试图检查一下实例是否之前已经被唤醒，是，则直接取出。即将已计算过实例的结果制表备查

改进方法二，方法更加通用，而且更加自然（动态规划：dynamic programming）
由自顶而下递归，改为自底而上迭代，“每个台阶”上只需要停留一次

+代码

f = 0; g =1; //fib(0), fib(1)while (0 < n--){g = g + f;f = g - f; //感受一下这步的精妙
}
return g;

呈现一种交替的滚动的方式，直到得到最后的解，与n成线性关系，只需要g和f两个存储单元，空间上是常数空间，

实例，最长公共子序列

概念，子序列，邻边彼此不能交叉
最长公共子序列，特殊情况，可能同时有多个公共子序列，这里将模型简化，不考虑特殊情况

+思维方法
按Kent Beck所建议的工作流程，暂时把计算效率放在一边，首先建立一个正确的可行的方案
方案一，递归求解
可能的三种情况：1）至少一个为空集，2）末字符相同，3）末字符不同（对称考虑两种情况，如图解有两种情况，即考虑两个递归实例）原问题的解无非是，两个子问题中的最长者
+问题，效率不高
绘制成表格理解整个计算过程
右下角（红色方块）为原问题的解，同时存在多条通路的情况，如上图

正确性和复杂度分析

• 单调性，无论如何，每经过一次比对，问题的规模必可减小。
  最好情况（不出现第二种情况）下，只需O(n+m)时间
• 但在第二种情况，原问题讲分解为两个子问题，更糟糕的是，它们在随后进一步导出的子问题，总而造成整体上大量雷同，与fib实例，完全类似

一个更宏观的角度：

• 把其中所有的递归实例，按坐标的形式表示为（n,m）或(0,0)；
• 为了计算出算法复杂度的最终结果，先考虑我们唤醒(a, b)递归实例的通路次数
• 考虑特例(0,0)的情况，若n = m（整个区域为方形），总数大致为O（2^n）

动态规划的策略，“似拙实巧”的方法

让计算的方向“颠倒”过来
逐行逐列进行填写

对于任何一个单元，根据具体情况（减而治之or分而治之）来选择如何处理

具体来看：

• 分而治之，左上角对应元素+1(如图中a行a列得到数值2)
• 减而治之，取上方和左侧元素，取最大值（如图t行c列得到数值2）
• 从行再到列，取法是安全的、准确的

方向为最初向左向上的逆向策略
任何一个子问题都只需要计算一次，颠倒次序以后的迭代式的计算过程，复杂度恰好等于表格的规模O(n*m)

+总结
递归：设计出可行且正确的解
动态规划：消除了重复计算，提高效率改进成了实用的算法，

缓存

缓存作用，拿出来，放到唾手可得的地方去
类比：书架和书包
书包：所有学习工具的子集，不同学期不同天会变化，在局部时间被高效实用

就地循环问题

仅用O(1)辅助空间，将数组A[0,n)中的元素向左循环移动k个单元

统一接口：void shift(intA, int n , int k);
第一种，蛮力版
考虑最基本的动作，移动一位，通过while循环反复移动一位
共迭代k次，O(nk)

第二种，“占坑”循环的迭代版—— 数论同余——封闭散列的一种状态，迟早会回到原位

• 但并不保证，所有数都能被检视到 改进
• 从起始点下一位也做一次同余列的“直奔主题”的就位
• O(greatest common divisor) = O(GCD(n,k))

另一解法，Reverse

+直观，用坡度代表数组的前后
将区间翻转—— 就地算法（形似彩虹）

复杂度，n/2 * 3（交换三句）*2（总长翻转两次） = 3n

邓俊辉老师看法
该算法给满分——什么原因？

连续储存

• 联系Cache序列—— 访问时，机器用cache装下最近用的最多的东西
• 多次使用以后，根据数据cache会用到这个数据或者附近的数据，装到更小的更高速的缓存中去，访问的是item，装进去的是一批数据
• 
  白色——外存，内存——绿色（几个数量级的差别）

进一步地，联系缓存机制思考，为什么前面的算法不好？ 为什么reverse算法，表面看起来3n，实际快？
—— 访问有规律性，虽也会周期性做一次I/O， 但周期变得更长，负担变得更小，效果反而更快

+本节重点
注意数据访问的姿势，彼此挨着的，走的有“规律”，“仆人”操作系统能更好发挥性能

向量

(a) 接口与实现
如何根据同一的接口，定制一个数据结构？
如何通过更有效的算法，使得对外的接口更高效率地工作？
——> 后续课程