algorithm - 我不明白这个算法的时间复杂度

Question

在一个练习中我发现一个复杂的算法:T(n)=c+2T(n−1)

可以由T(n)=c⋅2n 复杂度阶数为 O(2^n)。

有人知道怎么做吗？

Answer 1

_{@blazs 的回答似乎是正确的。如果这能帮助你理解，那就太好了。这是像我这样的视觉学习者的答案......}

---

您提供的循环是:T(n) = c + 2T(n−1)

• 因此，在递归树的每个节点上，您都在做一个恒定的工作 c。鉴于你在每个节点上所做的工作是恒定的，如果你能找到树中节点总数的上限，你就找到了复杂性!

• 根据您的递归，您有效地将一个大小为 n 的问题分解为两个大小为 n - 1 的问题。因此，在每一层，树实际上都会增长到上一层大小的两倍。它是一棵深度为n的完全二叉树。 ²完整二叉树中的节点总数由简单的公式 (2^{n - 1} - 1) 给出。

将它乘以 2，得到节点数与 2ⁿ - 2 成正比。因此，递归表示的复杂度为 = O(2 ⁿ).

---

一些有用的要点:

^{1。在递归树的方法中，算法的复杂度等于树的每一层所做工作的总和。}

^{2。 simple formula about the number of nodes in a complete binary tree高度 n。}

^{3. summation of powers of two in binary的优美解释在 Math StackExchange 上给出。}

^{4.您会看到如何通过解决两个大小为 n - 1 的问题来解决大小为 n 的问题。并且因为您多次解决每个子问题，所以最终会导致指数复杂度。如果您只解决一次 n - 1 大小的问题然后将其缓存以供将来查找，会发生什么情况？您可以将此问题的复杂性从 O(2n) 大大降低到 O(n)!!这种缓存称为内存，这种只解决一次子问题的方法有一个流行而可怕的名字动态编程。}