Praxisbeispiel für exponentielle zeitliche Komplexität
Ich suche ein intuitives, reales Beispiel für ein Problem, das (im schlimmsten Fall) exponentielle Zeitkomplexität erfordert, um eine Rede zu lösen, die ich halte.
Hier sind Beispiele für andere Zeitkomplexitäten, die ich mir ausgedacht habe (von denen viele aus this SO question ) stammen:
- O (1) - Bestimmen, ob eine Zahl gerade oder ungerade ist
- O(log N) - finding a Word in the dictionary (using binary search)
- O (N) - ein Buch lesen
- O(N log N) - sorting a deck of playing cards (using merge sort)
- O (N ^ 2) - Überprüfen, ob sich in Ihrem Einkaufswagen alles auf Ihrer Einkaufsliste befindet
- O (unendlich) - wirft eine Münze, bis sie auf den Köpfen landet
Irgendwelche Ideen?
- O(10^N): trying to break a password by testing every possible combination (assuming numerical password of length N)
p.s. warum ist dein letztes Beispiel Komplexität O(infinity)? Es ist eine lineare Suche O(N) .. es gibt weniger als 7 Milliarden Menschen auf der Welt.
Die brute-force-Lösung des Problems des reisenden Verkäufers ist O (n!), Was ungefähr O (N ^ N) ist.
Eine brutale und naive n-queens Problemlösung.
Du musst n Königinnen auf eine n * n Tafel setzen, ohne dass sie von anderen genommen werden.
while there are untried configs, go to next solution and test it
Unter der Annahme, dass sich jede Dame in einer bestimmten Reihe befindet, gibt es n Möglichkeiten für die Platzierung der Königin und n für die (n-1) anderen Königinnen (weil doppelte Reihen nicht geprüft werden).
Daher haben Sie eine O (n ^ n) -Komplexität
Wie wäre es mit einer Teilmenge von ganzen Zahlen innerhalb einer Menge, so dass ihre Summe ein bestimmter Wert X ist?
Ich glaube, das hat Komplexität O (2 ^ (n/2))