Какова временная сложность этой комбинации скобок? - PullRequest
Новая
       24

Какова временная сложность этой комбинации скобок?

0 голосов
/ 21 февраля 2019

Реализовать алгоритм для печати всех допустимых (иначе говоря, правильно открытых и закрытых) комбинаций из n пар скобок.
(Кстати, это вопрос из книги <Cracking coding interview> chp 8, вопрос 8.9)

Вот решение:

ParenthesesCombination.java : 

import java.util.LinkedList;
import java.util.List;

public class ParenthesesCombination {
    /**
     * Find all combinations with n pairs.
     *
     * @param n
     * @return
     */
    public static List<String> getAll(int n) {
        if (n < 1) throw new IllegalArgumentException("n should >= 1, but get: " + n);
        List<String> list = new LinkedList<>();

        getAll(n, n, 0, new char[n * 2], list);

        return list;
    }

    /**
     * Find cases with given buffer & index.
     *
     * @param leftRemaining  left remain count,
     * @param rightRemaining right remain count,
     * @param curIdx         current index in buffer,
     * @param buf            buffer,
     * @param list           result list,
     */
    protected static void getAll(int leftRemaining, int rightRemaining, int curIdx, char[] buf, List<String> list) {
        if (leftRemaining < 0 || rightRemaining < leftRemaining) return; // invalid, discard it,
        if (leftRemaining == 0 && rightRemaining == 0) {
            list.add(String.valueOf(buf)); // found, make a copy, and add,
            return;
        }

        // try to add '(',
        buf[curIdx] = '(';
        getAll(leftRemaining - 1, rightRemaining, curIdx + 1, buf, list);

        // try to add ')',
        buf[curIdx] = ')';
        getAll(leftRemaining, rightRemaining - 1, curIdx + 1, buf, list);
    }
}

Пример комбинации: 

pair count: 4, combination count: 14
     0: (((())))
     1: ((()()))
     2: ((())())
     3: ((()))()
     4: (()(()))
     5: (()()())
     6: (()())()
     7: (())(())
     8: (())()()
     9: ()((()))
    10: ()(()())
    11: ()(())()
    12: ()()(())
    13: ()()()()

Количество пар образцов и количество комбинаций: 

1 -> 1
2 -> 2
3 -> 5
4 -> 14
5 -> 42
6 -> 132
7 -> 429

В соответствии с алгоритмом оно должно быть между:

O(2^n) и O(4^n)

Но естьЕсть ли способ получить более точное время сложности?

1 Ответ

0 голосов
/ 21 февраля 2019

Точное количество выходных строк равно каталонским числам: https://en.m.wikipedia.org/wiki/Catalan_number. n-е каталонское число - это тета (4 ^ n / n ^ (3/2)), поэтому время работы - тета (4^ п / √n).

...