Wolfram Language

Algorithmen anhand von asymptotischen Beziehungen vergleichen

Im Bereich der Komplexitätstheorie werden Algorithmen nach ihrem Verhalten bei einer großen Eingabe (typischerweise bei einer unendlichen Menge von Instanzen) klassifiziert. Zwei Algorithmen werden in Hinblick auf ihre Zeitkomplexität vergleichen: Es wird unteruscht, ob die Rechenzeit des einen Algorithmus AsymptoticLessEqual (großes ), AsymptoticLess (kleines ), AsymptoticGreaterEqual (großes ) oder AsymptoticGreater (kleines ) als die Rechenzeit des anderen ist.

Das Problem des Handlungsreisenden besteht darin, die kürzeste Route durch Städte zu finden. Ein naiver Algorithmus probiert alle Routen durch. Der HeldKarp-Algorithmus verbessert dies auf etwa Schritte. Zeigen Sie, dass und somit der HeldKarp-Algorithmus schneller ist.

Beide Algorithmen zeigen, dass die Komplexitätsklasse des Problem des Handlungsreisenden nicht schlechter als EXPTIM ist, was für die Klasse der Entscheidungsprobleme steht, die in durch beschränkter Zeit entschieden werden können. Gilt zum Beispiel für , so hat der HeldKarp-Algorithmus exponentielle Laufzeit.

Für die Fakultät reicht eine lineare Exponentialfunktion nicht aus, da .

Allerdings hat die Fakultät immer noch eine exponentielle Laufzeit, da .

Approximationen können in der Zeit gefunden werden, also gehört das Problem des Handlungsreisenden zur Komplexitätsklasse P der in Polynomialzeit lösbaren Probleme. Jeder Polynomzeitalgorithmus ist schneller als ein exponentieller, oder .

Verwandte Beispiele

en es fr ja ko pt-br zh