なぜこのアルゴリズムはO（nlogn）ですか？

私はアルゴリズムの分析に関する本を読んでいて、時間の複雑さを得る方法がわからないアルゴリズムを見つけましたが、本にはO(nlogn)と書かれています。ここでなぜこのアルゴリズムはO（nlogn）ですか？

はアルゴリズムです：

sum1=0; 
for(k=1; k<=n; k*=2) 
    for(j=1; j<=n; j++) 
    sum1++;

出典

2016-09-02 Oberyn18

*私は時間の複雑さを得る方法を知らない、*鉛筆と紙を取る。 'n = 1'とすると、今度はコンピュータとなりアルゴリズムを実行します。もう一枚の紙を取って、「n = 2」と言い、もう一度コンピュータにしてください。 'n'のいくつかの小さな値を繰り返し、次に1つか2つの大きな値を繰り返します。理解が来るでしょう。 –

なぜこれに答えることができないのですか、正確には何が欠けていますか？ –

誰がそのような質問をアップアップしますか？ – xenteros

がa回外側のループfor(k=1; k<=n; k*=2)実行の数としよう...数学的なディテールのビットを追加します。その後、このループは2^a回実行されます（ループ増分はk*=2になります）。だから我々はn = 2^aを持っている。両側のベース2対数を取ることによってaのために解決し、あなたがa = log_2(n)

を取得する内部ループがn回実行されるため、合計がO(nlog_2(n))です。

出典

2016-09-02 14:35:31 qwerty

おそらくO(n*lgn)走行時間のことは自分を納得させるための最も簡単な方法は、紙にアルゴリズムを実行することです。 nが64を次に外側ループ変数kは、次の値を取るときに何が起こるかを考える：

1 2 4 8 16 32 64

log_2(64)は、上記プラスワン用語の数である、8です。この推論の行を続行して、外部ループが実行時間がO(lgn)になると判断できます。

内側ループは、外側ループとは完全に独立していますが、O(n)です。これらの2つの項を掛け合わせると、O(lgn*n)が得られます。

出典

2016-09-02 14:23:28

最初のループfor(k=1; k<=n; k*=2)では、変数kはの値がlog nステップに達し、各ステップの値が倍増しているためです。

第2ループfor(j=1; j<=n; j++)は単なる線形サイクルなので、nステップが必要です。

したがって、ループはネストされているので、合計時間はO(nlogn)です。

出典

2016-09-02 14:24:47

なぜこのアルゴリズムはO（nlogn）ですか？

答えて

関連する問題