复发T（n）= T（n - log（n））+ 1

Question

你如何找到这样的递推关系的严格界限？这是一个重要的问题，我们期望证明m/log（m）是严格的渐近界。我尝试使用感应，但它似乎无处可去。这是要么我缺少对数规则或有更多的东西。

Answer 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是作为一个练习。