ネストされたループの時間の複雑さ式

Question

アルゴリズムに関するこのステージ2コンプシックペーパーを始めたばかりですが、このようなものは私の強みではありません。講義スライドでこれに出くわしました。

int length = input.length();
for (int i = 0; i < length - 1; i++) {
    for (int j = i + 1; j < length; j++) {
        System.out.println(input.substring(i,j));
    }
}

「各反復で、外側のループは$ frac {n^{2} - （2i-1）n-i+i^{2}} {2} $操作を$ i = 0、に実行します。 ldots、n-1 $。」

誰かが私に段階的に説明してもらえますか？

上記の式は、数字を追加するためにGaussの式を使用して得られたと思います...

Answer 1

あなたの直感は正しいです、作業はあなたが一緒に追加するものを特定することです。

最初のビットは、長さの文字列$ m $を印刷するには$ m $ operationsが必要なので、

System.out.println(input.substring(i,j));

ラインには$ ji $操作が必要です。 （ここでのサイドノートは、私が非常に間違っていない限り、このコードはJavaにあるということです。 substring(start, end) メソッドは、インデックスから始まるサブストリングを提供します start で終わります end-1)

したがって、外側のループの各反復で、私たちは一連の長さ1（index $ i $の文字だけ）から始まり、$ i $から始まり、文字列の終わり input.

それをより数学的にダッシュするために、長さの文字列$ 1、2、 ldots、ni $を印刷しています。文字列の印刷に必要な操作の数はその長さと同じであるため、$ sum_ {k = 1}^{ni} k $操作を行っています。ガウスの式をこの合計の代わりに、操作の数は$$ frac {（ni）（n-i+1）} {2} $$に等しいとわかります。

次に、すべてを掛けると、スライドにある式が得られます。

Answer 2

外から働きましょう。

for (int i = 0; i < length - 1; i++) {

明らかに、このループは$ n = mathtt {length} -1 $ timesで実行されるため、$ sum_ {i = 0}^{n-1} dots $があります。ループの本体（反復$ i $の場合）。中にはあります

for (int j = i + 1; j < length; j++) {

同様に翻訳できますが、$ sum_ {i = 0}^{n-1} sum_ {j = i+1}^{n} dots $を取得できます。最後になりましたが、最も内側の操作

    System.out.println(input.substring(i,j));

明らかに、$ ji $の手順（文字ごとに1つの操作）を取ると想定されています。

すべてをまとめると、私たちは得ます

$ qquad begin {align} t（n）＆= sum_ {i = 0}^{n -1} sum_ {j = i+1}^{n} j -i ＆= sum_ { i = 0}^{n -1} left [ left（ sum_ {j = i+1}^{n} j right） - （ni）i right] ＆= sum_ {i = 0}^{n -1} left [ left（ sum_ {j = 1}^{n} j - sum_ {j = 1}^{i} j right） - （ni）i 右] ＆= sum_ {i = 0}^{n -1} left [ left（ frac {n（n+1）} {2} - frac {i（i+1）} {2} {2} {2} - frac {i（i+1）} right） - （ni）i right] ＆= sum_ {i = 0}^{n -1} left [ frac {n^2-（2i -1）n + i^2 -i } {2} right] end {align} $

括弧内の用語はあなたが探しているものです。

全体の合計は、Gaussの式とそれを使用して評価できます Summand $ i^2 $の兄弟:

$ qquad begin {align} 2t（n）＆= sum_ {i = 0}^{n-1} n^2 - sum_ {i = 0}^{n-1} 2in + sum_ {i sum_ {i = 0}^{n-1} n + sum_ {i = 0}^{n-1} i^2 - sum_ {i = 0}^{n-1} i ＆= n^3- 2n cdot sum_ {i = 0}^{n-1} i + n^2 + sum_ {i = 0}^{n-1} i^2- sum_ {i = 0}^{n- 1} i ＆= n^3 -n^2（n -1） + n^2 + frac {（n -1）n（2n -1）} {6} - frac {n（n- 1）} {2} ＆= frac {12n^2 + 2n^3-3n^2 + n -3n^2 + 3n} {6} ＆= frac {2n^3 + 6n^2 + 4n} {6} end {align} $

すぐに生成されます

$ qquad displaystyle t（n）= frac {n^3 + 3n^2 + 2n} {6} $。