この関数の時間の複雑さはどのくらいですか？

cs.stackexchange https://cs.stackexchange.com/questions/2487

質問

これは私の講義ノートの例です。この関数は、時間の複雑さ$ o（n log n）$？最悪の場合は、Funtionが入ることだからです else branch、および$ log n $と$ n $の時間の複雑さを伴う2つのネストループなので、$ o（n log n）$です。私は正しいですか？

int j = 3;
int k = j * n / 345;
if(k > 100){
    System.out.println("k: " + k);
}else{
    for(int i=1; i<n; i*=2){
        for(int j=0; j<i; j++){
            k++;
        }
    }
}
役に立ちましたか？

解決

言及されたアルゴリズムの時間の複雑さは$ o（1）$です。$ k> 100 $の場合、一定の動作（println）があり、$ j = 3、k = 3 cdot n / 345 が100 =を暗示するため3 cdot n / 345 はn = 11500 $を意味します。

もっと明確にするために、見てみましょう これ 質問。

他のヒント

編集：Saeed Amiriが指摘したように、これは実際には$ O（1）$です。なぜなら、漸近的に大きな$ n $の場合、 else ブランチは実際には撮影されていません。 if 部分が実行されますが、これは簡単に一定の時間です。私が参照するために残すこの答えの残りは、たとえば条件があった場合、正しいでしょう k < 100. 。混乱してすみません。

時間複雑度は、本質的に$ k $がネストされている回数の回数になります for ループ。いくつかの余分なことが進行中ですが、それについて考えると、それは一定の要因で遊んでいるだけです。 $ k $は何回増加しますか？

$ i = 1 $、$ k $が一度増加すると。 $ i = 2 $、$ k $がさらに2回インクリメントされます。 $ i = x $、$ k $が追加時間x $ x $を増やします。ここで、$ n = 2^m + 1 $と仮定しましょう。その後、内側ループの最後の反復が引き起こします k $ 2^m $の$ 2を増やす。

$ k $は、$ 1 + 2 + ... + 2^m $の総計、または$ 2^{（m + 1）} -1 $ timesで増分されます。 `$ n = 2^m + 1 $を思い出してください。したがって、$ n -1 = 2^m $、そして$ k $が$ 2（n -1） - 合計1倍に増分されていることがあります。

$ k $は、$ n $で線形である数回増加します。 ergo、これはすべて$ o（n）$です。

IF/他の枝についてのコメントはすべて正しいですが、答えはO（log n）です。その理由はそれです

System.out.println("k: " + k);

整数から弦の出力への変換を伴うと、これは一般的なケースでO（log n）になります（ルックアップテーブルが使用された場合でも、各数字を印刷するためだけに）。

それが質問のトリック部分であったかどうかはわかりません...

どれどれ：

int j = 3; 一定の時間がかかりますo（1）。

int k = j * n / 345 の対数時間関数を取得します j と n 変数

if (k > 100) 一定の時間がかかりますo（1）。

System.out.println("k: " + k); の対数時間関数を取得します k

for (int i=1; i<n; i*=2) の対数時間関数を取得します n, 、θ（log（n））は正確であるためです。 t ループのこれの反復数であり、の値は 私 次のように表現できます。 i = 2T-1, 、 もしも t = 1 最初の反復では、ループは 2T-1 <n, 、 どこ n 変化していません。

計算で、if 2T-1 <n それから T-1 <log2（n）

で、もし T-1 <log2（n） それから t <log2（n）+1

そして、各反復で、 t 1が増加すると、ループの場合、これは本当にθ（log（n））時間がかかることがわかります。 ループ用のこの内部のコードの実行時間の複雑さが一定の場合、つまりo（1）もちろんです！

ループのためにこれには、ループ用の別のものがあります：

for (int j=0; j<i; j++) k++;

これを分析しましょう：

k++; 一定の時間、つまりo（1）時間がかかります。

そのため、ループの内側の実行時間の複雑さを分析することは興味深いことです。

どれどれ：

ループのこの内側のコードによると、あるように見えます 私 ループのこの内側の反復なので、それは実行時間です θ（i）, 、 だけでなく o（i）, 、そうするからですいいえ 真ん中を壊しますが、それを覚えておいてください i <n, 、ループ用の外側のため、最初は1回の反復が必要ですが i = 1, 、2回の繰り返し i = 2, 、4回の繰り返し i = 4, 、8回の繰り返し i = 8...など、ライン内のループの外側の端で自分自身を2倍にするので I*= 2, 、したがって、合計で実行は1+2+4+8+...繰り返しです しかし それまで i≥n したがって、この内側のループの可能な最大の反復数は、 i = n-1 最悪の事件に関しては、ループの内側の最後の実行で実行された場合、それは実行されました n-1 イテレーションなので、それが実行されました （n-1）/2 イテレーションとそれ以前は実行されました （n-1）/4 イテレーションとそれ以前は実行されました （n-1）/8 繰り返し...だから合計で実行は次のとおりです。

n-1 +（n-1）/2 +（n-1）/4 +（n-1）/8 ... =（n-1）（1 + 1/2 + 1/4 + 1/8 ...）=（n-1）（2）= 2n-2 =θ（n）

それを思い出します 1 + 1/2 + 1/4 + 1/8...=2 幾何学的なシーケンスのよく知られている合計です。

ループの外側がθ（log（n））を取ることを思い出してください

ループの内側はθ（n）を取ります。

の実行時間の複雑さ ループ内のループ用 ループの外側の実行時間の複雑さに、ループの内側の走行時間の複雑さを掛けたものであるため、θ（nlogn）の実行時間がかかります。

要約すると、この関数の実行時間は θ（nlogn）.

これがあなたの質問によく答え、実行時間の複雑さを分析する方法をよく教えてくれることを願っています。

ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top