1

次の C++ コードを考えてみましょう。

string s = "a";
for (int i = 0; i < n; i++) {
    s = s + s; // Concatenate s with itself.
}

通常、コード片の時間計算量を分析するときは、内側のループが実行する作業量を特定し、外側のループの実行回数を掛けます。ただし、この場合、構築される文字列がどんどん長くなるため、内側のループによって実行される作業の量は反復ごとに異なります。

このコードをどのように分析して、膨大な時間の複雑さを取得しますか?

4

1 に答える 1

4

この関数の時間計算量は Θ(2 n ) です。その理由を理解するために、関数が何をするかを見て、それを分析する方法を見てみましょう。

まず、n = 3 のループをたどってみましょう。反復 0 の前では、文字列sは string"a"です。s反復 0 は、 to makeの長さを 2 倍にしますs = "aa"。反復 1 は、 の長さを 2 倍にsしますs = "aaaa"。次に、反復 2 で の長さを 2 倍にして、sを作成しs = "aaaaaaaa"ます。

お気付きかもしれませんがk、ループを繰り返した後、文字列の長さsは 2 kになります。これは、文字列をそれ自体と連結するためにますます多くの作業が必要になるため、ループの各反復が完了するまでにますます時間がかかることを意味しsます。具体的には、ループのth 反復が完了するまでに Θ(2 kk )の時間がかかります。これは、ループ反復がサイズ 2 k+1の文字列を構築するためです。

この関数を分析できる 1 つの方法は、内側のループの最悪の場合の時間の複雑さにループの反復回数を掛けることです。各ループ反復が終了するまでに O(2 n ) の時間がかかり、n 回のループ反復があるため、このコードの終了には O(n · 2 n ) の時間がかかることがわかります。

ただし、この分析はあまり良くないことが判明しており、実際には、このコードの時間の複雑さを過大評価することになります。確かに、このコードは O(n · 2 n ) の時間で実行されますが、big-O 表記はコード片の実行時間に上限を与えることを思い出してください。これは、このコードの実行時間の増加率が n · 2 nの増加率を超えないことを意味しますが、これが正確な境界であることを意味するものではありません。実際、コードをより正確に見ると、より良い境界を得ることができます。

完了した作業をより適切に説明することから始めましょう。このループの作業は、次の 2 つの小さな部分に分割できます。

  • ループのヘッダーで行われた作業i。ループが完了したかどうかをインクリメントしてテストします。
  • 文字列をそれ自体と連結する、ループの本体で行われる作業。

ここで、これら 2 つの場所での作業を説明するときは、1 回の反復だけでなく、すべての反復で行われた作業の合計量を説明します。

これらの最初のもの、つまりループ ヘッダーによって行われる作業を見てみましょう。これは正確に n 回実行されます。毎回、コードのこの部分は O(1) の作業のみを行い、 をインクリメントiし、 に対してテストnし、ループを続行するかどうかを決定します。したがって、ここで行われる作業の合計は Θ(n) です。

次に、ループ本体を見てみましょう。前に見たように、反復 k は反復 k で長さ 2 k+1の文字列を作成します。これにはおよそ 2 k+1の時間がかかります。これをすべての反復にわたって合計すると、完了した作業は (大まかに言えば) であることがわかります。

2 1 + 2 2 + 2 3 + ... + 2 n+1 .

では、この金額は？前に、次のことに注意して、O(n · 2 n ) の範囲を取得しました。

2 1 + 2 2 + 2 3 + ... + 2 n+1 .

< 2 n+1 + 2 n+1 + 2 n+1 + ... + 2 n+1

= n · 2 n+1 = 2(n · 2 n ) = Θ(n · 2 n )

ただし、これは非常に弱い上限です。もっと注意を払えば、元の合計をa = 2 および r = 2の等比級数の合計として認識することができます。これを考えると、これらの項の合計は正確に

2 n+2 - 2 = 4(2 n ) - 2 = Θ(2 n )

言い換えれば、すべての反復にわたって、ループの本体によって実行される合計作業は Θ(2 n ) です。

ループによって実行される総作業量は、ループのメンテナンスで実行される作業と、ループの本体で実行される作業を加えたものになります。これは、Θ(2 n ) + Θ(n) = Θ(2 n ) になります。したがって、ループによって実行される合計作業は Θ(2 n ) です。これは非常に急速に成長しますが、最初の分析で得られた O(n · 2 n ) ほどの速さではありません。

つまり、ループを分析するときは、ループの反復回数にそのループの 1 回の反復で実行される最大作業量を掛けることで、保守的な上限を常に得ることができます。ただし、より正確な分析を行うと、多くの場合、はるかに優れた境界が得られます。

お役に立てれば！

于 2013-04-29T20:10:17.877 に答える