Antwort
Ein Algorithmus ist ein Polynom (hat eine Polynomlaufzeit), wenn für einige $ k, C > 0 $, seine Laufzeit für Eingaben der Größe $ n $ beträgt höchstens $ Cn ^ k $. Entsprechend ist ein Algorithmus polynomisch, wenn für einige $ k > 0 $ seine Laufzeit für Eingaben der Größe $ n $ $ O (n ^ k) $ beträgt. Dies umfasst lineare, quadratische, kubische und mehr. Andererseits sind Algorithmen mit exponentiellen Laufzeiten kein Polynom.
Dazwischen liegen Dinge – zum Beispiel der bekannteste Algorithmus zum Faktorisieren von Läufen in der Zeit $ O (\ exp (Cn ^ {1 / 3} \ log ^ {2/3} n)) $ für eine Konstante $ C > 0 $; Eine solche Laufzeit ist als subexponentiell bekannt. Andere Algorithmen könnten in der Zeit $ O (\ exp (A \ log ^ C n)) $ für einige $ A > 0 $ und $ C > 1 $, und diese werden als Quasi-Polynom bezeichnet. Ein solcher Algorithmus wurde kürzlich für diskretes Protokoll über kleine Merkmale beansprucht .
Kommentare
- Siehe auch hier .
- Was ist k und C?
- Dies sind Parameter.
- Konstante Zeitalgorithmen werden also als Polynom betrachtet, richtig?
- Konstante Zeitalgorithmen sind ein Sonderfall von Polynomzeitalgorithmen.
Antwort
Das Ausführen eines Algorithmus kann einige Rechenzeit in Anspruch nehmen. Dies hängt hauptsächlich davon ab, wie komplex der Algorithmus ist. Informatiker haben eine Möglichkeit gefunden, den Algorithmus anhand seines Verhaltens zu klassifizieren, wie viele Operationen er ausführen muss (mehr Operationen benötigen mehr Zeit).
Eine dieser Klassen zeigt die Komplexität der Polynomzeit. Das heißt, die Betriebskomplexität ist proportional zu $ n ^ c $, während n die Größe der Eingabe ist und c eine Konstante ist. Offensichtlich kommt der Name wegen $ n ^ c $, einem -Polynom .
Es gibt andere „Arten“ von Algorithmen, die unabhängig von der Größe der Eingabe eine konstante Zeit in Anspruch nehmen. Einige nehmen $ 2 ^ n $ Zeit in Anspruch (ja, die meiste Zeit wirklich slllooooww).
Ich habe es für den Laien etwas vereinfacht und möglicherweise Fehler eingeführt. Lesen Sie also mehr https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time
Kommentare
- Ich habe auf Wolfram gelesen, dass Polynomzeitalgorithmen " schnell " . Ich höre jedoch viele Leute sagen, dass sie logarithmische oder lineare Zeitalgorithmen gegenüber polynomiellen Zeitalgorithmen bevorzugen. Verstehe ich die Verwendung des Wortes " schnell " falsch?
- Logarithmisch und linear sind ebenfalls polynomisch. Ich denke, ' schnell ' bedeutet wahrscheinlich etwas wie ', das viel praktischer ist real use '.
Antwort
In Laienbegriffen die Laufzeit Ihres Algorithmus.
Die Reihenfolge der Algorithmen (Wachstum) kann in Big-Oh (O), Little-Oh (O), Omega (Ω) oder Theta (Θ) erfolgen.
Wenn Sie Probleme bei der Berechnung der RR haben, sehen Sie sich bitte einige Fragen an, die ich zuvor gestellt habe, und stimmen Sie ab, wenn Sie dies verstehen.
Angenommen, Sie haben eine for-Schleife:
for(i=1 to n) x++ Die Reihenfolge oder zeitliche Komplexität dieses Codeteils lautet: O (n)
Warum groß-oh? Weil wir den schlimmsten Fall wollen, in dem dieser Code ausgeführt wird.
Lesen Sie hier (diese definieren die Komplexität eines Algorithmus und informieren Sie darüber, wie Algorithmen in Polynomzeit ausgeführt werden):
http://en.wikipedia.org/wiki/NP_(complexity) http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-hard Zusammenfassung:
http://www.multiwingspan.co.uk/a23.php?page=types
Kommentare
- Dies ' beantwortet die Frage nicht genau: Polynomzeit ist nicht " die Laufzeit Ihres Algorithmus ". Stattdessen kann die Laufzeit eines Algorithmus polynomiell sein und so weiter. Sie könnten die Antwort verbessern, indem Sie sie präziser machen. Müssen wir zum Beispiel wirklich 3 Wikipedia-Artikel über etwas lesen oder müssen wir überhaupt etwas über Big Oh wissen?