Benutzer Diskussion:Matthäus Gdaniec

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

In den folgenden Beispielen ist stets als Funktion von zu verstehen.

Notation Bedeutung Anschauliche Erklärung Beispiele für Laufzeiten
ist konstant wächst nicht, wenn sich das Argument ändert.
logarithmisches Wachstum wächst ungefähr um einen konstanten Betrag, wenn sich das Argument verdoppelt.

Merke: Die Basis des Logarithmus ist egal.

Binäre Suche im sortierten Feld mit x Einträgen
Wachstum wie die Wurzelfunktion wächst ungefähr auf das doppelte, wenn sich das Argument vervierfacht
lineares Wachstum wächst ungefähr auf das doppelte, wenn sich das Argument verdoppelt. Suche im unsortierten Feld mit x Einträgen
Suche im sortierten Feld mit x Einträgen

Mergesort

quadratisches Wachstum wächst ungefähr auf das vierfache, wenn sich das Argument verdoppelt Einfache Algorithmen zum Sortieren von x Zahlen

Bubblesort

exponentielles Wachstum wächst ungefähr auf das doppelte, wenn sich das Argument um eins erhöht
faktorielles Wachstum wächst ungefähr um das -fache, wenn sich das Argument von auf erhöht.

Rechenbeispiele

[Quelltext bearbeiten]

Zu der Notation (Obereren Schranke)

Das Wachstum eines Polynoms ist nach -Notation beschränkt durch das Monom mit dem größten Grad, also durch .

Gegeben sei eine Funktion mit

Wahl c & :

Das Monom mit größten Grad der Funktion ist

Graphen

wähle ( beide Werte zufällig gewählt )


Beweis:


Da

q.e.d.

Das Wachstum eines Polynoms ist nach -Notation beschränkt durch das Monom mit dem größten Grad, also durch .