Laufzeitkomplexität < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Zeigen Sie, dass der Algorithmus NaiveSearch im Average Case Laufzeit [mm] $\Theta(n)$ [/mm] hat. Nehmen
Sie hierzu an, dass sowohl der Text der Länge n als auch das Muster der Länge m zufällig
und gleichverteilt aus einem Alphabet mit [mm] $|\Sigma| \geq [/mm] 2$ Buchstaben gewählt werden. Die Aussage
folgt sofort, wenn Sie zeigen, dass die erwartete Anzahl an Buchstaben-Vergleichen durch
folgende Formel gegeben ist:
$(n-m+1) [mm] \cdot \frac{1-|\Sigma|^{-m}}{1-|\Sigma|^{-1}} \leq [/mm] 2(n-m+1) = [mm] \Theta(n)$ [/mm] |
Hi Leute!
Wie die Aufgabe sagt, soll ich ja durch Umformung dieses Terms die gegebene Laufzeitkomplexität einer naiven Suche verifizieren. Ich hab dann mal soweit es mir möglich umgeformt:
$(n-m+1) [mm] \cdot \frac{1-|\Sigma|^{-m}}{1-|\Sigma|^{-1}} \leq [/mm] 2(n-m+1) = [mm] \Theta(n)$
[/mm]
An dieser Stelle bringe $(n-m+1)$ auf die andere Seite. Ich denke man muss Ungleichheitszeichen nicht drehen, da der zu dividierende Teil nicht kleiner 0 wird. So wie ich die Angabe jedenfalls verstanden habe.
[mm] $\Leftrightarrow \frac{1-|\Sigma|^{-m}}{1-|\Sigma|^{-1}} \leq [/mm] 2 = [mm] \Theta(n)$
[/mm]
Allerdings weiß ich nun an dieser Stelle nicht mehr weiter, weil ich nicht weiß, wie ich nun mit [mm] $1-|\Sigma|^{-1}$ [/mm] im Zähler des Bruches umgehen soll... Ich mein da ist ja ein Alphabet gegeben und keine algebraische Variable!
Könnt ihr mir helfen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Mi 13.06.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:36 Mo 18.06.2012 | | Autor: | felixf |
Moin!
> Zeigen Sie, dass der Algorithmus NaiveSearch im Average
> Case Laufzeit [mm]\Theta(n)[/mm] hat. Nehmen
> Sie hierzu an, dass sowohl der Text der Länge n als auch
> das Muster der Länge m zufällig
> und gleichverteilt aus einem Alphabet mit [mm]|\Sigma| \geq 2[/mm]
> Buchstaben gewählt werden. Die Aussage
> folgt sofort, wenn Sie zeigen, dass die erwartete Anzahl
> an Buchstaben-Vergleichen durch
> folgende Formel gegeben ist:
>
>
> [mm](n-m+1) \cdot \frac{1-|\Sigma|^{-m}}{1-|\Sigma|^{-1}} \leq 2(n-m+1) = \Theta(n)[/mm]
>
>
> Hi Leute!
>
> Wie die Aufgabe sagt, soll ich ja durch Umformung dieses
> Terms die gegebene Laufzeitkomplexität einer naiven Suche
> verifizieren. Ich hab dann mal soweit es mir möglich
> umgeformt:
>
> [mm](n-m+1) \cdot \frac{1-|\Sigma|^{-m}}{1-|\Sigma|^{-1}} \leq 2(n-m+1) = \Theta(n)[/mm]
>
> An dieser Stelle bringe [mm](n-m+1)[/mm] auf die andere Seite. Ich
> denke man muss Ungleichheitszeichen nicht drehen, da der zu
Du hast hier etwas falsch verstanden!
Du sollst zeigen, dass die erwartete Anzahl an Buchstaben-Vergleichen durch den Ausdruck $(n-m+1) [mm] \cdot \frac{1-|\Sigma|^{-m}}{1-|\Sigma|^{-1}}$ [/mm] gegeben ist.
Dieser wird dann in der Aufgabenstellung abgeschaetzt, um zu zeigen, dass dieser in $O(n)$ liegt -- was dir die eine Haelfte des Endresultats der Aufgabe liefert.
Um das zu bekommen musst du jedoch erstmal den Ausdruck beweisen. Die Abschaetzung ist ein sehr einfacher Schritt im Vergleich dazu.
LG Felix
|
|
|
|
