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