C++ 数据结构(一)绪论(6)动态规划(1)
in C/C++ with 0 comment, Views is 80

C++ 数据结构(一)绪论(6)动态规划(1)

in C/C++ with 0 comment, Views is 80

上一篇:《C++ 数据结构(一)绪论(5)迭代与递归(3)》

fib():递归

$ fib(n) = fib(n-1) + fib(n-2):{0, 1, 1, 2, 3, 5, 8 ...} $

int fib(n) {
    return (2 > n) ? n : fib(n - 1) + fib(n - 2);
}

fib():递推方程

$$ \begin{align} 复杂度:& \begin{cases} T(0) = T(1) = 1 \\ \\ T(n) = T(n - 1) + T(n - 2) + 1 \; , \; n > 1 \end{cases} \\ \\ 令:& 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) \\ & T(n) = 2 * S(n) - 1 = 2 * fib(n + 1) - 1 = O(fib(n + 1)) = O(\phi^n) = O(2^n) \end{align} $$

fib():封底估算

$ \phi = \frac{1 + \sqrt{5}}{2} = 1.61803 \cdots $

fib() 计算第 43 项大致需要 1 s

$$ \begin{align} & \phi^{36} \approx 2^{25} \\ \\ & \phi^{43} \approx 2^{30} \approx 10^9 flo \approx 1 sec \\ \end{align} $$

fib() 计算第 67 项大致需要 1 day

$$ \begin{align} & \phi^5 \approx 10 \\ \\ & \phi^{67} \approx 10^{14} flo \approx 10^5 sec \approx 1 day \end{align} $$

fib() 计算第 92 项大致需要 3 century

$$ \phi^{92} \approx 10^{19} flo \approx 10^{10} sec \approx 10^5 day \approx 3 century $$

fib():递归跟踪

1.png

递归版 fib() 低效的根源在于,各递归实例均被大量重复调用

fib():迭代

解决方法A:记忆

memoization:将已计算过实例的结果制表备查

解决方法B:动态规划

dynamic programming:颠倒计算方向,由自顶而下递归改为自底而上迭代

3.png

f = 0; g = 1; // fib(0); fib(1)
while (o < n--) {
    g = g + f;
    f = g - f;
}
return g;

$ T(n) = O(n),而且仅需 \ O(1) \ 空间 $

nf g
00 1
111 - 011 + 0
212 - 121 + 1
323 - 132 + 1
435 - 253 + 2
...f g
...f'g' - fg'g + f

下一篇:《C++ 数据结构(一)绪论(6)动态规划(2)》

Responses
选择表情