递归和大O.

我一直在研究最近的计算机科学作业,包括递归和大O符号.我相信我很了解这一点(当然不是很完美!)但是有一个问题特别是给我最多的问题.奇怪的是,通过观察,它看起来是家庭作业中最简单的一个.

使用big-Oh表示法提供最佳增长率,以解决以下重现问题？

T(1)= 2

对于n> 1,T(n)= 2T(n-1)+ 1

选择是:

O(n log n)

为O(n ^ 2)

O(2 ^ n)的

为O(n ^ n)的

我知道大O作为一个上限,用于描述该程序或过程将采取的大部分计算或最高运行时间.我觉得这个特殊的递归应该是O(n),因为最多只有n的每个值都会发生一次递归.由于n不可用,它要么比那更好,O(nlogn),或者更糟糕的是,作为其他三个选项.

所以,我的问题是:为什么不是这个O(n)？

有几种不同的方法可以解决重现:替换,递归树和主定理.主定理在这种情况下不起作用,因为它不适合主定理形式.

您可以使用其他两种方法,但解决此问题的最简单方法是迭代地解决它.

T(n)= 2T(n-1)+
1T(n)= 4T(n-2)+ 2 +
1T(n)= 8T(n-3)+ 4 + 2 +
1T(n)= ...

看模式？

T(n)= 2 ^n-1· T(1)+ 2 ^n-2 + 2 ^n-3 + ... + 1
T(n)= 2 ^n- 1⋅2+ 2 ^n-2 + 2 ^{n- 3} + ... + 1
T(n)= 2 ⁿ + 2 ^n-2 + 2 ^n-3 + ... + 1

因此,最严格的界限是Θ(2 ⁿ).

我想你有点误解了这个问题.它没有问你解决复发需要多长时间.它问的是解决方案本身的大O(渐近界限)是什么.

你要做的是提出一个封闭形式的解决方案,即T(n)的非递归公式,然后确定该表达式的大O是什么.