algorithm - 递归算法的运行时

Question

对于上面的算法，我只能算出运行时间

if n==0:

是 1 并且运行时间为

rec_opt(n-1)

将是 T(n-1)。但我无法弄清楚运行时间

rec_opt(p[n])

以及为什么递归具有指数封闭形式，O(2^n)

此外，为什么这个算法会是 O(n)。

Answer 1

rec_opt(p[n])

对于递归调用 rec_opt(p[n])，将有另一个递归树，其作用类似于 rec_opt(n-1)。由于 p[n] 可以是 1 - n 中的任何值，因此我们可以假设它的行为类似于 rec_opt(n)。

And furthermore, why this algorithm will be O(n).

作为算法做的第二部分memoization ，它不会一次又一次地计算同一个子问题。这就是复杂性大幅降低到 O(n) 的原因。

更多请查dynamic programming .