我最近一直在完成一项涉及递归和大 O 符号的计算机科学作业。我相信我很清楚这一点(当然,当然不是很完美!)但是有一个问题特别给我带来了最多的问题。奇怪的是,看着它,它看起来是家庭作业中最简单的。
使用 big-Oh 表示法提供最佳增长率以解决以下递归问题?
T(1) = 2
T(n) = 2T(n - 1) + 1 对于 n>1
选择是:
我知道大 O 是一个上限,用于描述该程序或进程将花费的最多计算量或最长运行时间。我觉得这个特定的递归应该是 O(n),因为,对于 n 的每个值,最多只发生一次递归。由于 n 不可用,它要么比 O(nlogn) 好,要么更糟,作为其他三个选项。
所以,我的问题是:为什么这不是 O(n)?
最佳答案
有几种不同的方法可以解决递归问题:替换、递归树和主定理。主定理在这种情况下不起作用,因为它不符合主定理的形式。
您可以使用其他两种方法,但解决此问题的最简单方法是迭代解决。
T(n) = 2T(n-1) + 1
T(n) = 4T(n-2) + 2 + 1
T(n) = 8T(n-3) + 4 + 2 + 1
T(n) = ...
看到图案了吗?
T(n) = 2n-1⋅T(1) + 2n-2 + 2n-3 + ... + 1
T(n) = 2n-1⋅2 + 2n-2 + 2n-3 + ... + 1
T(n) = 2n + 2n-2 + 2n-3 + ... + 1
因此,最严格的界限是 Θ(2n)。
关于递归和大 O,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/206094/