确定重复的 BigO

Question

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

我如何快速确定 BigO？

Answer 1

使用重复回代，并找到图案。一个例子此处。

Answer 2

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

根据沃尔夫勒姆·阿尔法, ，递推方程解为：

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

是：

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

这将使这 O(n).

Answer 3

那么，关系的复发部分是T（N / 2）的一部分，这是在效果减半每个时间的值n。

因此，你将需要约（LOG2 n）的步骤获得的终止条件，因此该算法的总成本是O（LOG2 N）。可以忽略的dn一部分是它为每个工序的固定时间操作。

请注意，如所述的，该问题将不一定因为减半的任意值终止Ñ反复不可能准确击中1.我怀疑是T（N / 2）的部分实际上应T（地面（N / 2））或类似的东西，以确保此终止。

Answer 4

使用主定理 请参阅 http://en.wikipedia.org/wiki/Master_theorem

顺便提及，你的复发的渐近行为是O（n）假设d是正的并且大于n足够小（的问题的大小）