Laufzeit von Algorithmen beweisen

In diesen Artikel, gehe ich auf die Laufzeiten von Algorithmen im allgemeinen ein. Ich werde einmal erklären wie man Laufzeiten angibt und welche Besonderheiten es gibt. Diese Beschreibung von Algorithmen wird aber Plattformunabhängig sein, da man nicht den Einfluss von Hardware in dieser Angabe berücksichtigen möchte.

O-Notation

Um Laufzeiten für Algorithmen anzugeben, benutzt man die O-Notation. Mit dieser Notation kann man Grenzen angeben. Man kann zum Beispiel eine obere Grenze oder auch untere Grenze angeben. Damit legt man einfach fest, dass ein Algorithmus entweder maximal oder mindestens so viel Zeit braucht.

Diese Laufzeiten werden meistens für Algorithmen mit einer Eingabegröße von n angegeben. n Steht hier einfach für die anzahl an Problemen die gelöst werden müssen. Als Beispiel hat (vereinfacht) die Zuweisung von Variablen eine Laufzeit von genau einer Zeiteinheit. Schauen wir uns jetzt die verschiedenen Symbole und deren Bezeichnung an:

Bezeichnung	Bedeutung	Mathematik dahinter
O(n)	Maximal n Zeit	g(n) = O(f(n)) => g(n) ⪬ c*f(n)
Θ(n)	Genau n Zeit	g(n) = Θ(f(n)) => g(n) = c*f(n)
Ω(n)	Mindestens n Zeit	g(n) = Ω(f(n)) => g(n) ⪭ c*f(n)

Damit haben wir einmal die wichtigsten Bezeichnungen für die Beschreibung von Algorithmen. In der Tabelle stehen g(n) -> Zeit und f(n) -> Zeit für eine beliebige Funktion in ℝ. Das c ist eine Konstante, wobei aber gilt c > 0.

Auch wenn das c existiert kann man also sagen, dass ein Algorithmus mit der Laufzeit von 4*n trotzdem im lim(n) gegen n läuft da das c bei größer werdenden c immer weniger Einfluss hat.

Laufzeiten

In der Laufzeitanalyse gibt es bestimmte Laufzeiten, die wichtig sind bzw. oftmals auftreten. Beispiele dafür sind:

Laufzeit	Erklärung
Θ(1)	Konstante Laufzeit
Θ(log(n))	Logarithmische Laufzeit
Θ(n)	Lineare Laufzeit
Θ(n log(n)	Linear logarithmische Laufzeit
Θ(n2 )	Quadratische Laufzeit
Θ(nn )	Exponentiele Laufzeit
Θ(n!)	Faktorielle Laufzeit

Im nächsten Kapitel beweisen wir als Beispiel einige Laufzeiten und ob sie in einer bestimmten Laufzeit enthalten sind.

Beispiele

Aufgabe 1: Beweise oder Widerlege folgende Laufzeit-Äquivalenz n³ = O(n³ -2n² )

Lösung:

Diese Aufgabe ist eine typische Beweisaufgabe wie man sie aus der Mathematik kennt. Man kann diese Aufgabentypen mit mehreren Möglichkeiten lösen. Ich werde hier aber eine Art verwenden, die ähnlich zu Induktionsbeweisen ist.

Anleitung:

• Ein c ∈ {c ∈ ℝ : c > 0} finden.
• n₀ finden

n³ = O(n³ -2n² ) | Mathematische Schreibweise anwenden g(n) < c* f(n)

n³ ⪬ c*(n³ -2n² ) | n=1

1³ ⪬ c*(1³ -2*1² )

1 ⪬ c*(1-2) | Umstellen

-1⪬ c | für n₀ = 1 somit kein c mit den genannten Eigenschaften

________________________________________________________________________________________________________________

n³ ⪬ c*(n³ -2n² ) | n=3

3³ ⪬ c*(3³ -2*3² ) | n=1

27⪬ 9c

3⪬c | c=3 gefunden bei n₀ = 3

Antwort: Da wir ein konstantes c bei einen n₀ = 3 finden konnten, können wir sagen, dass die Laufzeit n³ in O(n³ -2n² ) enthalten ist. Macht soweit auch Sinn, weil wenn wir lim(n³ -2n² ) betrachten wird 2n² bei n gegen unendlich irgendwann keine Relevants haben und insgesammt wird die Funktion gegen n³ laufen.

Ergänzende Erklärung: n₀ ist also der Zeitpunkt für den Algorithmus, wo wir ein c mit den genannten Bedingungen finde. Ab diesen Zeitpunkt ist für uns die Betrachtung der Laufzeit wichtig

Algorithmus in O(n² )

Jetzt gehen wir mal anders dran. Man kann einerseits natürlich beweisen ob ein Algorithmus in einer bestimmten Zeit läuft aber genauso kann man auch einen Algorithmus entwickeln, der eine bestimmte Zeitvorgabe haben soll.

Aufgabe: Implementiere einen Algorithmus der in Laufzeit O(n² ) läuft. Hierbei ist egal was der Algorithmus genau berechnet, es ist nur die Laufzeit von O(n² ) wichtig!

Lösung:

procedure calcSomething(arr : int[])
     for i = 0 until i = arr.length do
         for j = 0 until j = arr.length do
              arr[i] = i*j

Der angegebene Algorithmus löst das Problem in quadratischer Zeit, weil wir als Eingabegröße ein Array der größe n haben. Für einen durchlauf durch das gesamte Array benötigt man somit n Zeit. Da wir dieses Array sogar verschachtelt durchgehen ergibt sich eine Laufzeit von O(n² ) für die Schleifen. Das wird auch nicht durch die Operation im Inneren beeinflusst, weil es eine einfache Rechenoperation ist, die konstante Zeit benötigt und bei größer werdenden n eine immer geringere Gewichtung für das Gesamtergebnis hat.

Für weitere Tipps zum Entwickeln von Algorithmen habe ich hier auch noch einen anderen Artikel für dich.

Weitere Lernquellen

Hier habe ich außerdem noch ein Video von einem bekannten Youtuber, welcher das Thema auch nochmal ausführlich.

Quellen

https://de.wikipedia.org/wiki/Zeitkomplexit%C3%A4t (Besucht am 18.06.2023)

https://pixabay.com/de/vectors/laptop-infografik-online-gesch%C3%A4ft-6087062/ (Besucht am 21.06.2023)