Вычисление сложности алгоритма для печати всех допустимых (т.е. правильно открытых и закрытых) комбинаций n-пар скобок
Мне бы хотелось, чтобы ваше мнение о временной и пространственной сложности этого алгоритма, который я реализовал (в Python), вычисляло сложность алгоритма для печати всех допустимых (т.е. правильно открытых и закрытых) комбинаций n-пар скобок (см. Все допустимые комбинации n-пара круглых скобок)
def find_par_n(n):
s = set(["()"])
for i in range(2, n + 1):
set_to_add = set()
for str_ in s:
set_temp = set()
ana = set()
for j in range(len(str_) + 1):
str_c = str_[0:j] + '(' + str_[j:]
if str_c in ana:
continue
ana.add(str_c)
for k in range(j + 1, len(str_) + 1):
str_a = str_c
str_a = str_a[0:k] + ')' + str_a[k:]
set_temp.add(str_a)
set_to_add.update(set_temp)
s = set_to_add
return s
Скорее всего, алгоритм можно улучшить с точки зрения времени и пространства. Пожалуйста, поделитесь своими мыслями.
5 ответов
Давайте попробуем с более простой версией.
Некоторые теоремы:
- Правильно спаренная струна имеет ровную длину. Не проси меня доказать это, пожалуйста.
- Учитывая правильно спаренную строку длины
2k, можно построить все строки длины2(k + 1)вставив пары скобок'()'в каждом возможном месте в строке. Есть2k + 1такие позиции. - Сгенерировать все
nпары, нам нужно рекурсивно в шаг вставкиnраз (и получить строки длины2n,
Обратите внимание, что этого недостаточно для генерации всех уникальных правильно спаренных строк, потому что, например, вставка () в () выдает одну и ту же строку дважды (()()). Однако в качестве верхней границы этого должно быть достаточно.
def add_parens(s, nparens):
if not s:
add_parens('()', nparens)
max_length = 2 * nparens
if len(s) == max_length:
print(s)
else:
for i in range(0, len(s)):
add_parens(s[0:i] + '()' + s[i:], nparens)
n = 5
add_parens('', n)
Сложность времени:
- Есть
1точка вставки для пустой строки. - Есть
3точки вставки для(),...
Итак, всего:
T(n) = 1 * 3 * ... * 2n + 1 ~ O(n!)
Пространственная сложность для рекурсивной версии O(n(2n + 1))Однако я почти уверен, что это можно привести к линейному.
Для достижения оптимальных результатов избегайте наборов. Если вы генерируете каждую возможность ровно один раз, вы можете просто поместить их в вектор.
Вот очень простая рекурсия, которая немного медленнее, чем ответ @ bcdan:
def rget(n):
if n == 0:
return ['']
else:
return [fst + '(' + snd + ')' for i in range(n)
for fst in rget(i)
for snd in rget(n-i-1)]
Если вам нужен генератор, а не полный список результатов, вариант вышеупомянутого, вероятно, является идеальным, но для случая полного списка гораздо быстрее вычислить результаты каждого j от 0 до n, используя ранее вычисленные списки вместо рекурсивного вызова:
def iget(n):
res = [['']]
for j in range(1, n+1):
res.append([fst + '(' + snd + ')' for i in range(j)
for fst in rget(i)
for snd in rget(j-i-1)])
return res[n]
Это оказывается на порядок быстрее (используя Python 3.3.2).
Почему это работает
Вы можете разложить любую сбалансированную строку на две сбалансированные подстроки. Это не уникальная декомпозиция, но ее можно сделать уникальной, выбрав максимально короткий непустой сбалансированный суффикс. Самый короткий непустой сбалансированный суффикс обладает свойством, что стартовый ( соответствует закрытию ); если бы это было не так, его можно было бы разложить на две более короткие непустые сбалансированные последовательности. Таким образом, рекурсивный состоит из поиска всех последовательностей вида Fst(Snd) где сумма размеров Fst и Snd равна n-1.
Сложность времени:
Число сбалансированных последовательностей с n парами скобок равно n-му каталонскому числу Cn, которое равно O (4nn2/3). Приведенный выше код генерирует каждую последовательность в O (n) (поскольку конкатенация строк занимает время O (n)) для общей сложности O (4nn5/3)
Количество возможных комбинаций - каталонский номер. Таким образом, сложность по крайней мере та, которая указана этим числом. https://en.wikipedia.org/wiki/Catalan_number
Рекурсивная версия кажется очень простой и тратит время только на допустимые ветки:
def gen(sofar, l, r, n):
"""
sofar: string generated so far
l: used left parentheses
r: used right parentheses
n: total required pairs
"""
result = []
if l == n and r == n:
# solution found
result.append(sofar)
else:
if l > r:
# can close
result.extend(gen(sofar + ")", l, r + 1, n))
if l < n:
# can open
result.extend(gen(sofar + "(", l + 1, r, n))
return result
def generate(n):
return gen("", 0, 0, n)
print generate(4)
Я стал любопытным и написал свою собственную версию. Вот некоторые характеристики (это все в Python 2.7):
n=8
Моя: 21 мс
Твое: 89 мс
n=10
Моя: 294 мс
Твое: 1564 мс
def get(n):
def find(current):
out = []
last_index = 0
for j in range(current.count('(')):
last_index = current.index('(',last_index) + 1
out.append(current[:last_index] + '()' + current[last_index:])
return out
seed = '()'
current = '()'
temp = set(['()'])
for i in range(n):
new = set()
for thing in temp:
new.update(find(thing))
temp = new
return [a[1:-1] for a in temp]
Я думаю, что самая большая разница в том, что у меня есть только 3 для циклов, а у вас 4. Это происходит на str.count функция. Использование этой встроенной функции, вероятно, значительно увеличивает скорость. Кроме того, после каждой стадии я идентифицировал дубликаты, и это сокращает экспоненциально по времени.
На самом деле, самое большое различие, которое я вижу, заключается в том, что я вставляю только после круглых скобок, а затем удаляю два внешних по окончании. Это создает намного меньше дубликатов. Так ((())()) создан и приведен к правильной форме (())() после снятия ограждающих (),