复发T(n)= T(n - log(n))+ 1
问题描述:
你如何找到这样的递推关系的严格界限?这是一个重要的问题,我们期望证明m/log(m)是严格的渐近界。我尝试使用感应,但它似乎无处可去。这是要么我缺少对数规则或有更多的东西。复发T(n)= T(n - log(n))+ 1
答
感应。假设所有k < n
的T(k) <= C k/log k
对于某些C
。
展开复发(n/2)/log(n/2)
次,更换log(.)
与log(n/2)
(我们利用的事实,即T(n)
和log(n)
是单调函数)。也就是说,
T(n) <= T(n - log(n/2) * (n/2)/log(n/2)) + (n/2)/log(n/2)
T(n) <= T(n/2) + (n/2)/log(n/2)
T(n) <= C (n/2)/log(n/2) + (n/2)/log(n/2)
现在你要证明右边的表达被C n/log n
界。算术和找到这样的C
是作为一个练习。
告诉我们你如何开始归纳,也许有人可以从那里帮助你。 – ShadowMitia