単純な時間の複雑さO（nlogn）

Question

私はインタビューのためにいくつかのビッグO表記を見直しており、私はこの問題に遭遇します。

for i = 1 to n do: 
    j = i 
    while j < n do: 
    j = 2 * j 

単純なのですか？外部ループはnステップを提供する。これらのステップのそれぞれは、j=iという1つのステップO（1）を実行し、その後、whileループに対してj = iステップからlog（n-j）またはlog（n-i）を実行します。時間の複雑さはO（nlogn）だと思ったが、答えはO（n）だった。

実行している時間は、およそ以下の合計です：Σ 1 + ログ（N/I）iに対する1からnまでΘ（n）は、ここで

が答えです。

今はちょっと錆びています。 log(n/i)はどこから来ますか？私はlog(n) - log(i) = log(n/i)を知っているが、私はlog（n-i）log（n） - log（i）をログすると思った。時間の複雑さはどのようにO（nlogn）ではないのですか？私は何かシンプルなものを見逃していると確信していますが、私はこれを数時間前から見つめています。私は心を失い始めています。

ソース：ここでは、この問題のソースはBerkeley CS 170, Fall 2009, HW 1

編集です：もう少しそれについて考えた後、それは内部ループの時間複雑性はログ（N/I）であることを意味します。それぞれの内側ループはn-i回実行されますが、私はそれぞれのループを2倍にします。内側のループが常に0から始まっていれば、log（n）がありますが、ループする必要のないループの数はlog（i）です。 log（n）-log（i）はlog（n/i）である。

Answer 1

IはI = 2（nは言う= 10することができます）とき意味ログ（N/I）内側のループから来

予告どのようj = i

に内部ループ

を考えます

while j < n do: 
    j = 2 * j 

j=2から10 2によるj個のmultilplies自体（したがってログ）& QUにのみ実行されますickly n=10

の値をオーバーランしそう内部ループは私はほとんどの時間、内部ループは一度だけ実行されるため、それは線形時間のように見える10 &コードを=シンプルに走ったlog base 2 n/i times

を実行します。

例：iの値が2になるとn以上になるような値になると、内部ループを複数回実行しません。

そうであれば、N = 10あなたは内側のループ内の1回の実行が i=n/2 (if i=10/2=5)から始まる取得後、jは、J = 5で始まるループが一回2 & while j < n do:が失敗した内部ループ状態で自身を乗算して取得します。

EDIT：//数学：jの値がJ = 0毎回&内側のループはiがn