T (1) = c
T (n) = T (n/2) + dn
我将如何快速确定 BigO？
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 回答