Двоичная последовательность длины просто упорядоченная последовательность , так что каждый является либо или . Чтобы сгенерировать все такие двоичные последовательности, можно использовать очевидную структуру двоичного дерева следующим образом: корень «пустой», но каждый левый дочерний элемент соответствует добавлению к существующей строке, а каждый правый дочерний элемент - , Теперь каждая двоичная последовательность - это просто путь длиной начинающийся с корня и заканчивающийся на листе.
Вот мой вопрос:
Можем ли мы добиться большего успеха, если хотим создать только двоичные строки длиной которые имеют ровно нулей и единиц?
Под «мы можем сделать лучше» я имею в виду, что мы должны иметь меньшую сложность, чем глупый алгоритм, который сначала строит все дерево выше, а затем пытается найти те пути с равным количеством «левого» и «правого» ребер.
источник
Ответы:
Очевидно, есть двоичных строк длиной . Чтобы пройти через двоичный файл, алгоритм должен посетить каждый узел один раз, т.е.4n 2n
Давайте рассмотрим рекурсивный алгоритм, который обходит дерево, которое вы описали, но подсчитывает количество единиц и нулей на своем пути, то есть он будет проходить только хорошую часть дерева.n n n 2n
Но сколько таких двоичных строк с 0 и 1 есть? Мы выбираем 1 для наших строк длиной и используем формулу Стирлинга на шаге 2:
РЕДАКТИРОВАТЬ
Благодаря комментариям Питера Шора мы также можем проанализировать количество шагов, необходимых для второго алгоритма, который считает 1 и 0. Я цитирую его комментарий снизу:
Снова используя формулу Стирлинга, мы получаем как время работы нового алгоритма.
источник
Возможно, я хладнокровен, но в первоначальном вопросе был задан способ генерации всех «сбалансированных» двоичных последовательностей длины 2n, который был бы более эффективным, чем обход дерева всех двоичных последовательностей длины 2n и вывод только тех, которые были сбалансированы. Так зачем вообще использовать дерево?
Вот псевдокод для рекурсивного алгоритма, который генерирует все такие последовательности (ключевое слово «yield» отправляет последовательность на выход):
Если я что-то неправильно понимаю, пожалуйста, скажите мне, но мне кажется, что это наиболее эффективный ответ на поставленную проблему, который никогда не определял использование дерева.
источник