Сложность времени для сочетания скобок

Question

Я попытался сделать классическую задачу, чтобы реализовать алгоритм для печати всех допустимых комбинаций 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/its-all-about-catalan/)

Какие временные сложности на ваш взгляд? Можем ли мы применить основную теорему здесь или нет?

Answer 1

Сложность этого кода O(n * Cat(n)), где Cat (n) - это n-е каталонское число. Существуют возможные допустимые строки Cat (n), которые являются допустимыми комбинациями скобок (см. https://en.wikipedia.org/wiki/Catalan_number), и для каждой создается строка длиной n.

Поскольку Cat(n) = выбирать (2n, n) / (n + 1), O(n * Cat(n)) = O(выбирать (2n, n)) = O(4^n / sqrt(n)) (см. https://en.wikipedia.org/wiki/Central_binomial_coefficient).

В ваших рассуждениях есть два основных недостатка. Во-первых, дерево поиска не сбалансировано: дерево, которое вы ищите при закрытии правой скобки, не совпадает с размером дерева, которое вы ищете при добавлении еще одной левой скобки, поэтому более распространенные методы вычисления сложности не работают., Вторая ошибка в том, что даже если вы предполагаете, что дерево сбалансировано, высота дерева поиска будет равна 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).