time - 您如何计算出通过检查运行程序需要多长时间？

Question

前几天我去了一个关于算法的讲座，我们正在学习动态规划。讲师提到，递归求解斐波那契将花费接近指数的时间，而以线性方式进行求解将花费二次时间。您如何仅通过检查就可以解决这种问题？

Answer 1

如果您只使用递归实现（没有记忆）
来确定 f_n，您需要计算 f_n-1 和 f_n-2，类似地，
f_n-1 将分支到 f_n-2 和 f_n-3，对于 f_n-2 也是如此。
因此，如果有这样的分支并且没有任何重用概念，请尝试计算节点。大多数情况下它将> 2 ^ n，
这意味着指数运行时间。
但是，如果您使用线性方式（如您所述），它将是线性的O(n) 甚至不是二次的！

但是您必须小心诸如合并排序之类的分而治之算法，
尽管它使用二进制除法，树的深度将为 logn ，其中节点数将变为2^logn ，即等于 n。