algorithm - 确定复发的 BigO

Question

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

我将如何快速确定 BigO？

score 2 · Accepted Answer

2

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

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

score 2 · Accepted Answer

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

根据 Wolfram Alpha，递归方程解：

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

是：

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

这将使这个O(n)。

score 1 · Accepted Answer

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

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

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

score 0 · Accepted Answer

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

4 回答 4