0 Daumen
23 Aufrufe

Frage:


Code:Worauf bezieht sich no 3?
1)Worauf bezieht sich no 3 ? auf no 1 ( Anzahl der Versuche) oder auf non2( Anzahle der Elemente)?

2) Worauf bezieht sich no 4 ? auf no 1 ( Anzahl der Versuche) oder auf non2( Anzahle der Elemente)?

blob.png

Text erkannt:

tierung in einer echten Programmiersprache. 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 ein\}
von Versuche die der Anzahl der Elemente entspricht. Bei n Elementen werden also maximal \( \mathrm{n} \) Versuche gebratucht. Dies wirt ats lineare Komplexität (des Algorithmus) bezeichnet. Man sagt auch, dass die Komplexität wvon der Ordnung \( n_{*} \) ist. Definition: Eine Funktion \( f(n) \) st höchstens von der Ordnung der Funktion \( g(n) \) falls es eine Konstante C gibt, sodass fưr "große Ne 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. Bei anderen Algorithmen kann es völlig andere Komplexitätsklassen geben. Stellen Sie sich beispielsweise ein Programm vor, das nacheinander alle erdenklichen Reihenfolgen einer Folge von \( n \) verschiedenen Werten ausgeben soll - dieses Verfahren wird als Suche nach Permutationen bezeichnet. Für die Zahlenfolge \( 1,2,3 \) gibt es beispielsweise die folgenden Permutationen:

von

1 Antwort

0 Daumen
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.

von 3,3 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community