首页 > 代码库 > 数据结构 3动态规划

数据结构 3动态规划

Make it work---------------- 递归

Make it right---------------- 递归

Make it fast----------------- 迭代



 所谓的动态规划:就是用递归初步给出,让后用迭代等价的替换。

fib(n) = fib(n - 1) + fib(n -2) +...........+ ........   :  递归

T(n) = T(n - 1) + T(n - 2) + 1,n >1

s(n) = [T(n) + 1] / 2;

s(0) = 1 = fib(1) , s(1) = 1 = fib(2)

故 s(n) = s( n - 1) + s(n - 2) = fib(n + 1)

O(1.61803 的n次方) 就是那个黄金分隔数 = O(2的n次方)-------------------∮(黄金分割数)的36次方 = 2 的25次方(近似)

                           -------------------2 的10次方 = 10 的3次方(近似)

                          --------------------10 的 9次方操作数刚好是现在主流计算机的1秒钟操作数。 10 的9次方 flo = 1 sec

∮的5次方 = 10, 上段程序在计算机里计算到 第67 个 大概是10的14次方操作数 = 10 的5次方sec = 1day

 

数据结构 3动态规划