8

n ペアの括弧のすべての有効な組み合わせを出力するアルゴリズムを実装するために、古典的な問題を実行しようとしました。

このプログラムを見つけました（完全に機能します）：

public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
    if (leftRem < 0 || rightRem < leftRem) return; // invalid state

    if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
        String s = String.copyValueOf(str);
        list.add(s);
    } else {
        if (leftRem > 0) { // try a left paren, if there are some available
            str[count] = '(';
            addParen(list, leftRem - 1, rightRem, str, count + 1);
        }
        if (rightRem > leftRem) { // try a right paren, if there’s a matching left
            str[count] = ')';
            addParen(list, leftRem, rightRem - 1, str, count + 1);
        }
    }
}

public static ArrayList<String> generateParens(int count) {
    char[] str = new char[count*2];
    ArrayList<String> list = new ArrayList<String>();
    addParen(list, count, count, str, 0);
    return list;
}

私が理解しているように、可能な限り左括弧を追加するという考えです。右括弧の場合、右括弧の残りの数が左括弧より多い場合にのみ追加します。左右の括弧をすべて使用した場合は、新しい組み合わせを結果に追加します。重複して構築された文字列がないことを確認できます。

私にとって、この再帰は、たとえばツリーで作業し、たとえば事前注文トラバーサルを行うときのようなものです。左のノードに移動するたびに可能ですが、そうでない場合は右に移動し、次に左に移動しようとしますこのステップの直後。できない場合は、「戻ってきて」右に進み、トラバーサルを繰り返します。私の意見では、ここではまったく同じ考えです。

だから、単純に、時間の複雑さは O(log(n))、O(n.log(n)) のようなものになると思いました。しかし、それについて調べてみると、括弧の組み合わせの数を数える「カタランの数」というものを見つけました....( https://anonymouscoders.wordpress.com/2015/07 /20/そのすべて-カタロニア語/ )

あなたの意見では、時間の複雑さはどのくらいですか? ここで主定理を適用できるかどうか。

4

1 に答える 1

6

このコードの複雑さは O(n * Cat(n)) です。ここで、Cat(n) は n 番目のカタロニア数です。括弧の有効な組み合わせ ( https://en.wikipedia.org/wiki/Catalan_numberを参照) である Cat(n) 通りの有効な文字列があり、それぞれの長さ n の文字列が作成されます。

Cat(n) = choose(2n, n) / (n + 1) なので、O(n * Cat(n)) = O(choose(2n, n)) = O(4^n / sqrt(n)) ( https://en.wikipedia.org/wiki/Central_binomial_coefficientを参照)。

あなたの推論には 2 つの主な欠陥があります。1 つ目は、検索ツリーのバランスが取れていないことです。右ブレースを閉じるときに検索するツリーは、別の左ブレースを追加するときに検索するツリーと同じサイズではないため、複雑さを計算するためのより一般的な方法は機能しません。 . 2 つ目の間違いは、ツリーがバランスが取れていると仮定しても、検索ツリーの高さは n であり、見つかった葉の数は O(2^n) になるということです。これは、通常、ツリー内に n 個のものがあり、高さが O(log n) であるバイナリ サーチ ツリーの分析とは異なります。

ここで時間の複雑さを計算する標準的な方法はないと思います-最終的には、有効な括弧内の文字列を数えるときに行われる数学のようなものを再現することになります-マスター定理はあなたを力づけませんそれ。

しかし、ここで有用な洞察があります。プログラムが f(n) 個のものを生成し、それぞれを生成するコストが c(n) の場合、プログラムの複雑さは O(c(n)f(n) よりも優れていることはありません。 ）。ここで、f(n) = Cat(n) および c(n) = 2n であるため、コードの分析が困難な場合でも、複雑さの下限をすばやく取得できます。このトリックを使用すると、複雑さが O(log n) または O(n log n) であるという考えをすぐに破棄することになります。

于 2016-05-23T08:57:30.727 に答える