4

私は Sedgewick と Wayne による「アルゴリズム - 第 4 版」という本を読んでいますが、「アルゴリズムの分析」の章のいくつかの部分が私を混乱させていることを認めなければなりません! これはおそらく私の数学的な知識の不足が原因です... とにかく！

本のどこかに、内側のループが正確に N(N-1)(N-2)/6 回実行されると言われているプログラムの例があります。ここにあります：

    public static int count(int[] a) {
        int count = 0;

        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; i < a.length; j++) {
                for (int k = j + 1; k < a.length; k++) {
                    if (a[i] + a[j] + a[k] == 0) {
                        count++; 
                    } 
                }
            }
        }
        return count;
    }

ビッグ O 表記には慣れていますが、ループ内の操作の正確な数を数えることになると、途方に暮れます。N(N-1)(N-2) の部分は理解できましたが、なぜ 6 で割る必要があるのでしょうか? その背後にあるロジックは何ですか？

どんな助けでも大歓迎です！

4

4 に答える 4

7

その部分を理解できるならN(N-1)(N-2)、ここに考えがあります：

i、j、k の 3 つの数字の組み合わせを取り、その範囲に含まれる 30 <= i,j,k < Nつのうち、互いに異なるものを選びます (これもコードで考慮されているため、式はN(N-1)(N-2)and notN^3です。

さて、数字が 13、17、42 だとしましょう。それらがどの数字であるかは問題ではありません。それらを一列に並べる方法はいくつありますか?

13-17-42
13-42-17
17-13-42
17-42-13
42-13-17
42-17-13

六！

これらの方法のうち、コードに表示できるのはいくつですか? 唯一！(これは と の初期化で処理されますj) k。

したがって、 の合計数をN(N-1)(N-2)で割る必要があります6。

于 2012-08-11T14:37:29.557 に答える
4

シグマ表記を使用して、本で言及されている式を思いつく方法を発見できます。

ここに画像の説明を入力

于 2014-06-06T16:10:11.917 に答える
1

みなさんご存じのとおり...

1+2+3+4...+N => N(N-1)/2

同様に、最も内側のループは次のように機能します

1.n+2(N-1)+3(N-2)+...N.1 => N(N-1)(N-2)/6

これが証明です。

于 2012-08-11T14:37:52.647 に答える
1

6 は 3 から派生したものです。(3 つのループから派生した 3 つの階乗)。

たとえば、5 つの要素の配列の最も外側のループを考えてみましょう。方程式のその部分で N=5 を数えていますが、値 i=0、i=1、または i=2 の内側のループにしか到達しません。同様に、次のループを (N-1) で表していますが、値 j=1、j=2、または j=3 の内側のループにのみ到達し、(N-1 によって暗示される 4 つの値には到達しません) ）。

6 で割ると (3 つのループの場合)、最も内側のループに到達する前に配列内の値が不足する値が補正されます。

于 2012-08-11T15:23:01.070 に答える