在一个练习中我发现一个复杂的算法:T(n)=c+2T(n−1)
可以由 T(n)=c⋅2n 复杂度阶数为 O(2^n)。
有人知道怎么做吗?
最佳答案
@blazs 的回答似乎是正确的。如果这能帮助你理解,那就太好了。这是像我这样的视觉学习者的答案......
您提供的循环是:T(n) = c + 2T(n−1)
因此,在递归树的每个节点上,您都在做一个恒定的工作
c
。鉴于你在每个节点上所做的工作是恒定的,如果你能找到树中节点总数的上限,你就找到了复杂性!根据您的递归,您有效地将一个大小为 n 的问题分解为两个大小为 n - 1 的问题。因此,在每一层,树实际上都会增长到上一层大小的两倍。它是一棵深度为n的完全二叉树。 2完整二叉树中的节点总数由简单的公式 (2n - 1 - 1) 给出。
将它乘以 2,得到节点数与 2n - 2 成正比。因此,递归表示的复杂度为 = O(2 n).
一些有用的要点:
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)!!这种缓存称为内存,这种只解决一次子问题的方法有一个流行而可怕的名字动态编程。
关于algorithm - 我不明白这个算法的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36390038/