Big Theta und asymptotische Notation erklärt

Big Omega gibt die untere Grenze der Laufzeit einer Funktion an, und Big O gibt die obere Grenze an.

Oft sind sie unterschiedlich und wir können keine Garantie für die Laufzeit geben - sie variiert zwischen den beiden Grenzen und den Eingaben. Aber was passiert, wenn sie gleich sind? Dann können wir eine Theta (Θ) -Bindung geben - unsere Funktion wird in dieser Zeit ausgeführt, unabhängig davon, welche Eingabe wir geben.

Im Allgemeinen möchten wir nach Möglichkeit immer eine Theta-Grenze angeben, da dies die genaueste und engste Grenze ist. Wenn wir keine Theta-Grenze geben können, ist das nächstbeste die engste O-Grenze, die möglich ist.

Nehmen Sie zum Beispiel eine Funktion, die ein Array nach dem Wert 0 durchsucht:

def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false
  1. Was ist der beste Fall? Wenn das Array, das wir ihm geben, 0 als ersten Wert hat, dauert es konstant: Ω (1)
  2. Was ist der schlimmste Fall? Wenn das Array keine 0 enthält, haben wir das gesamte Array durchlaufen: O (n)

Wir haben ihm eine Omega-und-O-Bindung gegeben. Was ist also mit Theta? Wir können es nicht geben! Abhängig von dem Array, das wir ihm geben, liegt die Laufzeit irgendwo zwischen konstant und linear.

Lassen Sie uns unseren Code ein wenig ändern.

def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)

Können Sie sich einen besten und einen schlechtesten Fall vorstellen? Ich kann nicht! Egal welches Array wir ihm geben, wir müssen jeden Wert im Array durchlaufen. Die Funktion dauert also mindestens n Zeit (Ω (n)), aber wir wissen auch, dass sie nicht länger als n Zeit dauert (O (n)). Was bedeutet das? Unsere Funktion wird genau n Zeit dauern : Θ (n).

Wenn die Grenzen verwirrend sind, denken Sie so darüber nach. Wir haben 2 Zahlen, x und y. Wir erhalten, dass x <= y und dass y <= x. Wenn x kleiner oder gleich y ist und y kleiner oder gleich x ist, muss x gleich y sein!

Wenn Sie mit verknüpften Listen vertraut sind, testen Sie sich selbst und überlegen Sie sich die Laufzeiten für jede dieser Funktionen!

  1. erhalten
  2. entfernen
  3. hinzufügen

Noch interessanter wird es, wenn man eine doppelt verknüpfte Liste betrachtet!

Asymptotische Notation

Wie messen wir den Leistungswert von Algorithmen?

Überlegen Sie, wie viel Zeit eine unserer wertvollsten Ressourcen ist. Beim Rechnen können wir die Leistung anhand der Zeit messen, die ein Prozess benötigt, um abgeschlossen zu werden. Wenn die von zwei Algorithmen verarbeiteten Daten gleich sind, können wir uns für die beste Implementierung zur Lösung eines Problems entscheiden.

Dazu definieren wir die mathematischen Grenzen eines Algorithmus. Dies sind die Big-O-, Big-Omega- und Big-Theta-Notationen oder die asymptotischen Notationen eines Algorithmus. In einem Diagramm wäre das Big-O das längste, das ein Algorithmus für einen bestimmten Datensatz oder die „Obergrenze“ benötigen könnte. Big-Omega ist wie das Gegenteil von Big-O, der „Untergrenze“. Hier erreicht der Algorithmus seine Höchstgeschwindigkeit für jeden Datensatz. Big Theta ist entweder der genaue Leistungswert des Algorithmus oder ein nützlicher Bereich zwischen engen oberen und unteren Grenzen.

Einige Beispiele:

  • "Die Lieferung wird in Ihrem Leben da sein." (Big-O, Obergrenze)
  • "Ich kann dir mindestens einen Dollar bezahlen." (Big-Omega, Untergrenze)
  • "Das Hoch heute wird 25ºC sein und das Tief wird 19ºC sein." (Big-Theta, schmal)
  • "Es ist ein Kilometer zu Fuß zum Strand." (Big-Theta, genau)

Mehr Informationen:

//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-Notation-Repräsentation //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/