Ich führe einen implementierten Algorithmus. Ich habe die Laufzeit basierend auf den einzelnen Eingabedaten erfasst. Zum Beispiel ist in der ersten Spalte die Eingabegröße und in der zweiten Spalte die Laufzeit abhängig von der Eingabegröße. Gibt es trotzdem einen Hinweis darauf, dass die zeitliche Komplexität dieses Algorithmus exponentiell ist, basierend auf Eingabe und Laufzeit?Wie herauszufinden, Zeit Komplexität ist exponentiell?
Dank
Bei der ersten sollten Sie sich auf die Analyse des Algorithmus verlassen.
Der zweite - Datenbereich ist zu kurz, um das Kurvenverhalten zuverlässig zu bestimmen.
Im Allgemeinen könnten Sie den Logarithmus der Werte der zweiten Spalte berechnen. Für Exponenten sollte eine Darstellung von Log(F(x)) gegenüber x grob linear sein, weil (Formel wird bearbeitet)
Log(A * B^(C * x)) = Log(A) + x * (C/Log(B))
Was ist das Problem, das Sie versuchen zu lösen? Möchten Sie sehen, ob es für diese bestimmte Instanz exponentiell ist oder versuchen Sie, eine generische Vorgehensweise zu finden?
Wenn erste, Verwendung: http://www.shodor.org/interactivate/activities/SimplePlot/
Setzen Sie Ihre Punkte in
1,53
2,97
3,155
4,259
5,452
6,920
Hit Plot.. Aus der Form des Graphen sieht es wie exponentiell aus.
Wenn Sie versuchen, dies in der generischen Art und Weise zu lösen, sehen: https://www.khanacademy.org/math/algebra/introduction-to-exponential-functions/exponential-growth-and-decay/v/constructing-linear-and-exponential-functions-from-data Wenn Sie erraten, dass es exponentielle sind Sie können versuchen, zu sehen, was die params für eine bestimmte Form der Funktion ist. Sie sollten auch Fehler berücksichtigen (dh Sie können leicht unterschiedliche Funktionen für verschiedene Punkte erhalten)