Laufzeitanalyse < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:53 Mo 09.04.2007 | | Autor: | Bukso |
| Aufgabe | Bestimmen Sie jeweils die Werte für n, so dass Algorythmus A schneller ist als Algorythmus B.
a) A hat Laufzeit [mm] 4n^2
[/mm]
B hat Laufzeit 16n log2n
b) A hat Laufzeit [mm] 10n^2
[/mm]
B hat Laufzeit [mm] 2^n [/mm] |
Die Kode sollte in C(oder Java) ähnliche Notation sein.
Ich habe nachgedacht aber nicht auf eine richtige lösung gelandet. In der Vorlesung wurde uns die folgende Formel gegeben: Zeile - Kosten - Wie oft? .
z. B. Zeile: 1 Kosten: c1 Wie oft?: n. Leider kann ich nicht so viel damit anfangen, da meiner Meinung nach sich diese Formeln auf die Funktionen beziehen.
Ich würde sehr dankbar sein wenn mir jemand helfen könnte.
Gruss
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Bukso!
> Bestimmen Sie jeweils die Werte für n, so dass Algorythmus
> A schneller ist als Algorythmus B.
> a) A hat Laufzeit [mm]4n^2[/mm]
> B hat Laufzeit 16n log2n
>
> b) A hat Laufzeit [mm]10n^2[/mm]
> B hat Laufzeit [mm]2^n[/mm]
Damit A schneller ist als B, musst du in Teil a) ein n finden, so dass gilt: [mm] $4n^2<16n \log_2 [/mm] n$ (oder meinst du wirklich [mm] $\log [/mm] 2n$?) Also einfach die Ungleichung umformen, so dass da steht n<... oder n>... .
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:44 Mo 09.04.2007 | | Autor: | Bukso |
Ou, danke für deinen Schnellen Antwort.
Also eigentlich meine ich [mm] log_{2}n [/mm] . Beim 1 Teil bekomme ich also n < [mm] log_{2}n^4 [/mm] . Noch mal vielen Dank jetzt weiss ich wie das Geht :) und werds versuchen auch beim 2 Teil so was zu tun.
Gruss
|
|
|
| |
|
Hallo,
sitze an der gleichen Aufgabe...
habe das jetzt auch nach n aufgelöst und erhalte dann auch
n< [mm]log_{2}n^4[/mm] raus. aber damit kann ich doch nicht wirklich was anfagen, habe ja immernoch auf beiden seiten n stehen....
da habe ich doch nichts gewonnen...:-(
Kann mir jemand helfen, bzw. mich vielleicht aufklären??
Vielleicht verstehe ich das ja auch irgendwie falsch??
Viele GRüße, der mathedepp_No.1
|
|
|
| |
|
Wie Bastiane geschrieben hat, läuft das auf eine Ungleichung raus.
aber meines Erachtens ist es sinnlos zu probieren, die Lösung in eine Syntax zu packen.
am Einfachsten gehts es mit einer kleinen Tabelle. In die erste Spalte kommt n von 0 bis 10 erst mal, in die 2. Spalte die Ungleichung.
Dann Zeile für Zeile ausrechnen, sobald die Ungleichung nimmer stimmt, hast du die Lösung.
Mein Lösungsvorschlag (ohne Garantie):
a) n=2 (oder 3?)
b) n=0 (zwar Sinnlos, aber OK)
|
|
|
| |
|
also die exponentialfunktion ist die umkehrfunktion zur logarithmusfunktion.
wenn du beide seiten durch n teilst und versuchst einen ausdruck log(x)=n zu finden ,wärest du meiner meinung nach der lösung nahe.
|
|
|
|
