T (1) = c
T (n) = T (n/2) + dn
我将如何快速确定 BigO?
使用重复的反向替换并找到模式。这里有一个例子。
我不完全确定是什么dn
,但假设你的意思是一个常数乘以n
:
根据 Wolfram Alpha,递归方程解:
f(n) = f(n / 2) + cn
是:
f(n) = 2c(n - 1) + c1
这将使这个O(n)
。
好吧,关系的递归部分是 T(n/2) 部分,实际上每次都将 n 的值减半。
因此,您将需要大约。(log2 n) 步骤到达终止条件,因此算法的总成本为 O(log2 n)。您可以忽略 dn 部分,因为它是每个步骤的恒定时间操作。
请注意,如上所述,问题不一定会终止,因为将 n 的任意值减半不太可能完全达到 1。我怀疑 T(n/2) 部分实际上应该读取 T(floor (n / 2))或类似的东西,以确保终止。
使用大师定理见http://en.wikipedia.org/wiki/Master_theorem
顺便说一句,假设 d 为正且充分小于 n(问题的大小),您的递归的渐近行为是 O(n)