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 Held–Karp-Algorithmus verbessert dies auf etwa Schritte. Zeigen Sie, dass und somit der Held–Karp-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 Held–Karp-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 .