2
T (1) = c    
T (n) = T (n/2) + dn

我将如何快速确定 BigO?

4

4 回答 4

2

使用重复的反向替换并找到模式。这里有一个例子。

于 2010-10-31T00:08:32.280 回答
2

我不完全确定是什么dn,但假设你的意思是一个常数乘以n

根据 Wolfram Alpha,递归方程解:

f(n) = f(n / 2) + cn

是:

f(n) = 2c(n - 1) + c1

这将使这个O(n)

于 2010-10-31T00:13:02.373 回答
1

好吧,关系的递归部分是 T(n/2) 部分,实际上每次都将 n 的值减半。

因此,您将需要大约。(log2 n) 步骤到达终止条件,因此算法的总成本为 O(log2 n)。您可以忽略 dn 部分,因为它是每个步骤的恒定时间操作。

请注意,如上所述,问题不一定会终止,因为将 n 的任意值减半不太可能完全达到 1。我怀疑 T(n/2) 部分实际上应该读取 T(floor (n / 2))或类似的东西,以确保终止。

于 2010-10-31T00:18:55.597 回答
0

使用大师定理见http://en.wikipedia.org/wiki/Master_theorem

顺便说一句,假设 d 为正且充分小于 n(问题的大小),您的递归的渐近行为是 O(n)

于 2010-11-01T07:43:04.720 回答