Algorithmen und Datenstrukturen · Middle · Frage 48 von 75
Wie viele Teilmengen hat eine Menge mit n Elementen, und warum ist das wichtig?
- 12ⁿ, also ist das Erzeugen aller Teilmengen exponentiell
- 2n!, also ist das Erzeugen aller fakultätsartig
- 3n², also ist das Erzeugen aller quadratisch
Antwort zeigen
Richtige Antwort: 2ⁿ, also ist das Erzeugen aller Teilmengen exponentiell
Erklärung
Jedes Element ist entweder drin oder nicht, das ergibt 2ⁿ Kombinationen. Backtracking, das Teilmengen aufzählt, ist für n um 20 in Ordnung, aber nicht für 50. n! ist die Zahl der Permutationen.