Zum Forum springen
Suchaufgabe
 
Benachrichtigungen
Alles löschen

[Geschlossen] Suchaufgabe

2 Beiträge
2 Benutzer
0 Reactions
420 Ansichten
Allin5288
Beigetreten: 18.08.2006

Kann mir dabei jmd helfen???

Aufgabe:
Aus einem Vektor mit 1Millionen Zahlen suchen Sie eine Zahl.
Wieviele Suchschritte müssen Sie im Mittel ungefähr ausführen,

1. wenn der Vektor sortiert ist?
2. wenn er unsortiert ist?

Begründen Sie ihre Antwort.


1 Antwort
MadCow
Beigetreten: 15.09.2006

1. maximal log2(1 million) ~ 20
binäre suche (-> google)
quadratische binärsuche bei gleichverteilten daten sogar log(log2(n)) vermutlich aber nicht gefragt
2. 1 million /2