反復T（n）= T（n - log（n））+ 1

Question

このような反復関係にはどのようにしっかりとした境界がありますか？これはhw問題であり、m/log（m）が厳密な漸近線であることを証明することが期待されます。私は誘導を使ってみましたが、どこにも行かないようです。対数ルールで何かが欠けているか、それ以上のことがあります。

Answer 1

誘導。すべてk < nの場合はCの場合はT(k) <= C k/log kとします。

アンロール再発(n/2)/log(n/2)回、（私たちはT(n)とlog(n)両方が単調関数であるという事実を利用）log(n/2)でlog(.)を交換します。それは今、あなたは右の式はC 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)

です。 Arthmeticsとそのような発見はCです。