Binäre_Suche < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:18 Mi 13.01.2010 | | Autor: | jumape |
| Aufgabe | | Welche Genauigkeit hat die binäre Suche? |
Bei der binären Suche hat man im best case 1 Schritt, wenn das Element sich in der Mitte des Arrays befindet.
Im worst case findet man das element erst im letzten schritt. Wenn der Array [mm] n=2^k [/mm] Elemente hat sind es [mm] log_2(n) [/mm] Schritte. so ist dies die Komplexität.
Mein Problem ist der average case. In diesem fall ist die Komplexität:
[mm] C_(mit)=\bruch{1}{N} [/mm] (Gesamtkosten)
= [mm] \bruch{1}{N} \summe_{i=0}^{n-1}(i+1)2^i
[/mm]
= [mm] \bruch{1}{N} ((n-1)2^n+1)
[/mm]
= [mm] \bruch{1}{N}((N+1)log_2(N+1)-N)
[/mm]
[mm] \approx log_2(N+1)-1
[/mm]
für große N.
Eine andere Quelle besagt dass die Komplexität im average case [mm] log_2(N)-1 [/mm] beträgt.
Ich gehe davon aus, dass dieser Unterschied darauf zurückzuführen ist dass in einem fall davon ausgegangen wird dass [mm] N=2^n [/mm] ist und im anderen Fall von [mm] N=2^n-1.
[/mm]
Ist das richtig? Kann mir jemand zeigen wie ich den Beweis umändern kann dass [mm] log_2(N)-1 [/mm] das Ergebnis ist?
Vielen dank für die hilfe
|
|
| |
|
Hallo jumape,
> Welche Genauigkeit hat die binäre Suche?
> Bei der binären Suche hat man im best case 1 Schritt,
> wenn das Element sich in der Mitte des Arrays befindet.
![[ok]](/images/smileys/ok.gif "[ok]") ja, klar.
> Im worst case findet man das element erst im letzten
> schritt. Wenn der Array [mm]n=2^k[/mm] Elemente hat sind es [mm]log_2(n)[/mm]
> Schritte. so ist dies die Komplexität.
an sich , wobei aber [mm] log_2(n)=log_2(2^k)=k [/mm] ist. Also: k Schritte.
> Mein Problem ist der average case. In diesem fall ist die
> Komplexität:
> [mm]C_(mit)=\bruch{1}{N}[/mm] (Gesamtkosten)
> = [mm]\bruch{1}{N} \summe_{i=0}^{n-1}(i+1)2^i[/mm]
Moment. Was ist der Zusammenhang zwischen N und n?
> = [mm]\bruch{1}{N} ((n-1)2^n+1)[/mm]
> =
> [mm]\bruch{1}{N}((N+1)log_2(N+1)-N)[/mm]
> [mm]\approx log_2(N+1)-1[/mm]
> für große N.
Jaja. 5=2+2 für besonders große Werte von 2. Schon klar.
> Eine andere Quelle besagt dass die Komplexität im average
> case [mm]log_2(N)-1[/mm] beträgt.
Dann müsstest Du die Quellen mal genauer aufdröseln.
> Ich gehe davon aus, dass dieser Unterschied darauf
> zurückzuführen ist dass in einem fall davon ausgegangen
> wird dass [mm]N=2^n[/mm] ist und im anderen Fall von [mm]N=2^n-1.[/mm]
Aha. Woher weiß ich das als unbeteiligter Leser?
> Ist das richtig? Kann mir jemand zeigen wie ich den Beweis
> umändern kann dass [mm]log_2(N)-1[/mm] das Ergebnis ist?
Wenn N tatsächlich verschieden ist, scheinst Du das doch schon zu wissen. Wohin will dann die Frage?
> Vielen dank für die hilfe
lg
reverend
|
|
|
| |
|
> Komplexität:
> [mm]C_{(mit)}= ............\approx log_2(N+1)-1[/mm]
> für große N.
>
> Eine andere Quelle besagt dass die Komplexität im average
> case [mm]log_2(N)-1[/mm] beträgt.
>
> Ich gehe davon aus, dass dieser Unterschied darauf
> zurückzuführen ist dass in einem fall davon ausgegangen
> wird dass [mm]N=2^n[/mm] ist und im anderen Fall von [mm]N=2^n-1.[/mm]
>
> Ist das richtig? Kann mir jemand zeigen wie ich den Beweis
> umändern kann dass [mm]log_2(N)-1[/mm] das Ergebnis ist?
Da es sich ohnehin um eine Approximation handelt und
N groß sein soll, ist es praktisch auch einerlei, ob man nun
[mm] log_2(N+1)-1 [/mm] oder [mm] log_2(N)-1
[/mm]
nimmt. Für N=100 ist der relative Unterschied z.B. ein
viertel Prozent.
LG Al-Chw.
|
|
|
|
