再帰関係の漸近的解析

Question

未知のアルゴリズムの実行時間をモデル化する回帰関係があり、アルゴリズムの実行時間の下限、または上限と下限の両方を見つける必要があります。

許し粗い整形。 Latex-to-imageパーサ私は数式を奇妙に使用しました。各方程式の数は、数値の下にあるの左とです。

式（1）と（2）は、再帰関係の部分です。

式（2）〜（3）から、繰り返しの繰り返しをいくつか書き出し、形成するパターンを観察し、新しい変数kを使用して一般化します。

式（4）が成立すると、再帰が停止することに注意してください。

式（4）を式（3）に代入して式（5）を得る。また、ベース2の対数ですべてのログを取得するには、対数ベースの変更式を使用します。

式（5）から式（6）から、ビッグオー分析の式（5）についていくらかの観察を試みる。しかし、率直に言って、この最後のステップは私の考え方に過ぎません。

式（5）を仮定すると、は実際にはです。式（5）のtheta、omega、またはohをどのように表現すればよいでしょうか？

私は、nが非常に大きくなると、式（5）の動作を知ることに興味がありました。しかし、nが無限に近づくときの方程式（5）の限界は、負の数の対数を含みます。

何か助けていただければ幸いです。

Answer 1

指数関数から対数への変換が間違っています。確かに

(10/9)^k <= n <= (10/9)^(k+1). 

が進対数その後、

T(n) around T(1)+c*log2(n)/log2(10/9) 

になり

log2(n)/log2(10/9) - 1 <= k <= log2(n)/log2(10/9) 

のようにkの境界に変換することができ

k*log2(10/9) <= log2(n) <= (k+1)*log2(10/9) 

を適用するようないくつかのkが存在します

まだまだですlog2（n）の倍数で上下に拘束されますが、補正された式は「わずかに」異なります。