Warum erfordert diese iterative Klammergenerierung trotz der Generierung von Duplikaten weniger Operationen als der Divi ⇐ Python

[Anonymous]

Ich löse LeetCode 22 – Klammern generieren und habe mir einen iterativen Ansatz ausgedacht, der Kombinationen erstellt, indem er () an jeder (-Position einfügt, plus Voranstellen/Anhängen. Obwohl mein Ansatz doppelte Kandidaten generiert (von einer Menge behandelt), führt er weniger Iterationen innerhalb der Schleife durch als die Divide-and-Conquer-Lösung aus dem Leitartikel von LeetCode.
Meine Iteration Lösung:
Python

Code: Select all

def generateParenthesis(self, n: int) -> List[str]:
combinations = {"()"}
for _ in range(n - 1):
new_combinations = set()
for pattern in combinations:
new_combinations.add("()" + pattern)
new_combinations.add(pattern + "()")
for idx, char in enumerate(pattern):
if char == "(":
new_combinations.add(pattern[:idx + 1] + "()" + pattern[idx + 1:])
combinations = new_combinations
return list(combinations)

LeetCode-Editorial (Teile und herrsche):
Python

Code: Select all

def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return [""]
answer = []
for left_count in range(n):
for left_string in self.generateParenthesis(left_count):
for right_string in self.generateParenthesis(n - 1 - left_count):
answer.append("(" + left_string + ")" + right_string)
return answer

Gemessene Inner-Loop-Iterationen:



n
Meiner
Editorial




1
0
1


2
2
4


3
10
15


4
40
55


5
152
200



Beide erzeugen eine identische Ausgabe (verifiziert). Ich habe die innersten Schleifen instrumentiert: In meiner zähle ich Iterationen über Zeichen; Im Editorial zähle ich die innersten Append-Aufrufe.
Meine Fragen:

• Was erklärt den Unterschied in der Anzahl der Iterationen? Das Editorial generiert jede einzigartige Kombination genau einmal, während meines Duplikate generiert, die vom Set verworfen werden. Intuitiv würde ich erwarten, dass mein Ansatz mehr Arbeit leistet.
• Gibt es einen geschlossenen Ausdruck für die Anzahl der Iterationen, die jeder Ansatz als Funktion von n durchführt? Die Ausgabegröße ist die katalanische Zahl C(n), aber ich bin mir nicht sicher, wie ich die Iterationszahlen ableiten soll.
• Gilt die niedrigere Iterationszahl in meinem Ansatz asymptotisch, oder gewinnt der Leitartikel letztendlich für größere n?