Ich möchte wissen, ob es möglich ist, "ein Programm oder Algorithmus " zu schreiben, um die zeitliche Komplexität eines gegebenen Programms zu finden als Eingabe.
Eingabe: jedes Programm (P) [in einer beliebigen Sprache oder einer bestimmten Sprache]
Ausgabe: Zeitkomplexität des Programms (P).
Wurden bereits Versuche unternommen, ein solches Programm zu schreiben? Gibt es Algorithmen für diesen Zweck?
Wenn dies der Fall ist, geben Sie bitte die erforderlichen Links, Referenzen oder jegliche Art von Anleitung an.
Nein. Es ist nicht möglich. Dies ist eine Form des Problems beim Anhalten
Es ist nicht möglich, die Komplexität eines beliebigen Algorithmus nachzuweisen, aber im Prinzip könnte man es schätzen:
Es gibt eine Reihe von Fallstricken bei diesem Ansatz
Es gibt viele Möglichkeiten, wie dieser Ansatz getäuscht werden kann, wenn Sie nicht große Werte verwenden von n. Zum Beispiel wird dieser Algorithmus wie O (1) aussehen, es sei denn, Sie verwenden astronomische Werte für n
%Vor%Und andere SO-Benutzer können sich viel mehr einfallen lassen. Aber in manchen Fällen, etwa wenn Sie eine Komplexitätsanalyse eines Algorithmus durchführen und diese empirisch verifizieren möchten, ist dies immer noch ein nützlicher Ansatz.
können wir nicht noch mehr Variablen in den Algorithmus selbst einführen und die Komplexität auf die gleiche Art und Weise finden, wie wir es manuell tun. wie zum Beispiel können wir eine Variable in einer Einfügesortierung haben, sagen wir n = 0, die die Spur des gesamten Schleife-Teils des Algorithmus behält und dann die Antwort als O (n ^ 2)
gibtNun, ich denke, Sie tun dies, indem Sie alle Fälle annehmen. 1: Wie mache zuerst ein Modul, das jede Anweisung extrahieren kann 2: Erstellen Sie eine Datenbank mit Anweisungen, die der Programmanweisung entsprechen. 3: Berechnen Sie die Komplexität durch Abrufen der entsprechenden Zeitkomplexität, die Sie in der Datenbank festgelegt haben, und das ist alles.
Tags und Links algorithm time-complexity