Komplexität anderer Algorithmen als asymptotisch (Big-O-Notation)

Question

Was ist das meist übernommene Konzept, außer asymptotischer Komplexität (Big-O-Notation), um Algorithmen zu bewerten?

Beispiel:

I Gesetzt den folgenden Algorithmus haben, der eine Funktion aufruft, func, mit Komplexität O (1). Dann hätte dieser Algorithmus die Komplexität O (N1 × N2). Aber wenn ich vorher wüsste, dass N1 begrenzt ist [1,5], dann wäre die Worst-Case-Komplexität O (5 x N2), was definitionsgemäß auch O (N2) ist.

for i in range(N1): 
    for j in range(N2): 
     func(i,j) 

Im Fall kann ich auf einer andere Implementierung dieses Algorithmus ist eine Funktion func2 verwendet, wiederum mit Komplexität O (1), nun aber unterschiedlichen Außenschleifenbereich, N3 verwendet. Dieser Algorithmus würde O (N3 x N2) sein. Wenn ich jedoch wüsste, dass der Bereich von N3 [10,50] ist, dann wäre die Worst-Case-Komplexität O (50 x N2), was wiederum O (N2) ist.

for i in range(N3): 
    for j in range(N2): 
     func2(i,j) 

Frage:

Also, das ist eine einfache, dass asymptotisch Notation ist nützlich zu zeigen, aber vielleicht nicht die am besten geeignete Vergleichsmethode für einige speziellere Fälle. Wie kann ich diese beiden Algorithmen vergleichen? Was sind die am häufigsten verwendeten Methoden? Wird nur die Anzahl der für den Algorithmus erforderlichen Iterationen zu einer technisch strengen Metrik?

Beliebige Referenz?

Answer 1

Ihre Frage ist sehr groß. Informieren Sie sich über die Komplexität und die Metriken des Algorithmus.

Ihr Problem ist, dass selbst wenn Sie nicht Big-O verwenden (es gibt viele andere kleine-O Big-Omega, kleine Omega, Theta, etc.) Sie werden nicht in der Lage, Algorithmen leicht vergleichen, wie es ist scheint du willst! Der Hauptgrund ist, dass Sie zuerst klar definieren müssen, was Sie messen möchten, und das ist nicht einfach. Im Allgemeinen möchten Sie keine Details. Warum? Weil wir wissen, dass wir jeden Algorithmus immer linear beschleunigen können (grob gesagt, spezielle Fälle sind hier nicht relevant). Also ist die multiplikative Konstante nicht relevant.

Nun, was Sie wollen ist (weder Worst-Case, Best-Case oder Average-Case) mehr eine Vorhersagefunktion für die Laufzeit, die irgendwie zu einer genauen Komplexität verwandt ist. Aber selbst dort gibt es viele Fallstricke und Fallen. Sie können denken, dass zwei Algorithmen, die eine exakte Komplexität von beispielsweise 3n + 45 haben, auf derselben Plattform genauso schnell laufen, aber dies kann falsch sein! Wenn Sie nicht genau definieren, was Sie zählen, kann dies falsch sein. Man kann 3n-Multiplikationen verwenden und die anderen 3n-Additionen (oder feineres Mischen von) und die Laufzeit von Multiplikation und Addition sind im Allgemeinen nicht die gleichen. Am schlimmsten ist, dass die Architektur Pipelines, Vorhersagen und andere Laufzeitoptimierungen verwenden kann, was die Laufzeit drastisch verändern kann. Selbst die Umwelt-Plattform kann ernsthafte Voreingenommenheit einführen, über virtuellen Speicher denken, Caches, verschiedene Compiler-Optimierungen, etc.

Also die Antwort ist: es hängt davon ab, was Sie vorhersagen wollen ... Deshalb gibt es so viele Komplexitätsmaßnahmen.