Laufzeiteffizienz < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Ein String der Länge n belegt [mm]O(n)[/mm] Speicherplätze. Sei suffixes [als Haskell-Funktion] definiert als:
suffixes [] = [Leere Liste in leerer Liste]
suffixes xs = xs:(suffixes (tail xs))
Wie lautet die Laufzeiteffizienz für eine Liste der Länge n, was verwenden Sie als charakteristische Operation? |
Hallo zusammen,
ich steige hier leider nicht so recht durch, was die Aufgabe angeht.
Wie soll ich zunächst einmal die Laufzeiteffizienz bestimmen? Ist das damit die Einordnung des Algorithmus in eine Effizienzklasse gemeint?
Eine charakteristische Operation haben wir wie folgt definiert:
[mm]\mbox{wc-time}_{p \in A}(n) \in \Theta(\mbox{wc-time}_A(n))[/mm]
mit p = Operation, A = Algorithmus, wc-time = Worst-Case-Laufzeit
Eine Operation p, welche im Algorithmus A liegt, ist also dann eine charakteristische Operation, wenn sie in der Theta-Effizienzklasse von der Worst-Case-Laufzeit des Algorithmus liegt.
Um das bestimmen zu können, muss ich ja erst einmal die wc-time des Algorithmus bestimmen. Allerdings hat dieser Algorithmus doch ohnehin immer eine lineare Laufzeit, oder? Im Grunde geht das ja schon auf der Aufgabe hervor: Die (Best-Case-, Average-Case-, Worst-Case-) Laufzeit beträgt [mm]O(n)[/mm] oder auch [mm]\Theta(n)[/mm].
Damit könnte man schonmal festhalten:
[mm]\mbox{wc-time}_{p \in \mbox{suffixes}}(n) \in \Theta(n)[/mm]
Aber wie geht es von hier an jetzt weiter?
Viele Grüße
Patrick
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 So 16.12.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
