Worauf bezieht sich f(n)? Auf die "Anzahl der Versuche" oder auf die "Anzahl der Elemente"? (O-Notation)

Question

Frage:

1) Worauf bezieht sich f(n)? Auf die "Anzahl der Versuche" oder auf die "Anzahl der Elemente"?

2) Worauf bezieht sich g(n)? Auf die "Anzahl der Versuche" oder auf die "Anzahl der Elemente"?

Der Best Case ist das Finden des Werts beim ersten Versuch. Beim Worst Case müssen alle Elemente der Menge mit dem Suchwert verglichen werden. Der Average Case ist in diesem Fall die Hälfte der Elementanzahl. Die Komplexitătsklasse richtet sich grundsătzlich nach dem Worst Case, weil man bei der Programmierplanung berücksichtigen muss, wie lange die Ausführung eines Programms maximal dauern kann.

Der Algorithmus für die lineare Suche benötigt im Höchstfall eine Anzahl von Versuchen, die der Anzahl der Elemente entspricht. Bei n Elementen werden also maximal \( \mathrm{n} \) Versuche gebraucht. Dies wird als lineare Komplexität (des Algorithmus) bezeichnet. Man sagt auch, dass die Komplexität "von der Ordnung n" ist.

Definition: Eine Funktion \( f(n) \) ist höchstens von der Ordnung der Funktion \( g(n) \) falls es eine Konstante C gibt, sodass für "große" gilt: \( f(N) \leq C \times g(N) \)

Dies wird symbolisch auch als \( f(N)=O(g(N)) \) geschrieben - die sogenannte O-Notation (Big. O-Notation).

Bei der linearen Suche ist \( g(N)=N \), sodass für die Funktion \( f(N) \) gilt:
\( \mathrm{f}(\mathrm{N})=\mathrm{O}(\mathrm{N}) \)

Übrigens spricht man auch dann von ein und derselben Komplexitätsklasse, wenn sich die Anzahl der Durchläufe zweier Algorithmen um einen konstanten Faktor voneinander unterscheidet. Benötigt ein anderer Algorithmus für \( n \) Elemente beispielsweise \( 2 n \) Versuche, wird dies ebenfalls als lineare Komplexität angegeben.

Answer 1

falls es eine Konstante C gibt, sodass fưr "große Ne gilt:\( f(N) \leq C \times g(N) \)

In dem Beispiel mit der linearen Suche ist N die Anzahl der Elemente und f(N) die Anzahl der Versuche.

Wenn du einen Algorithmus gegeben hast, dann steht damit f(N) fest. Bei der Laufzeitanalyse des Algorithmus ist die Aufgabe, ein möglichst kleines g(N) zu finden.