O-Notation < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:11 Do 30.06.2011 | | Autor: | JBourne |
| Aufgabe | Ein Algorithmus benötige 5 mS um ein gegebenes Problem für eine Zahlenfolge der Länge n = 100 zu lösen. Wie lange wird der Algorithmus laufen wenn die Zahlenfolge n = 200, n = 400, n = 800, n= 1600 Zahlen enthält und die Zeitkomplexität von der Ordnung
1) n
2) [mm] n^{2}
[/mm]
3) [mm] log_{2}
[/mm]
4) n [mm] log_{2} [/mm] n ist. |
Unsere Professorin hat mit uns Alle Fälle berechnet, doch mir scheint es so, als ob die Rechnung von ihr falsch war
1) n, ist gar kein Problem
doch bei [mm] n^{2} [/mm] hat Sie als Ergebnis
(bei 100 -> 5ms, bei 200 -> 20ms, bei 400-> 80ms, bei 800 ->320ms, bei 1600 1280 ms)
ich komme aber auf:
(bei 100 -> 5ms, bei 200 -> 100ms, bei 400-> 400ms, bei 800 ->1600ms, bei 1600 -> 6400 ms)
dabei berechnete ich es so:
[mm] n_{0}= [/mm] 5ms
[mm] n_{1} [/mm] = [mm] 2*n_{0} [/mm] -> [mm] (2*n_{0})^{2}
[/mm]
Bsp für 200, ( [mm] 2*100)^{2} [/mm] = 400
Wer hat Recht? Falls ich falsch liege, wo ist da dann mein Fehler?
und mit [mm] log_{2}, [/mm] n [mm] log_{2} [/mm] n kann ich leider nichts anfangen.
Vielen Dank im Voraus!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo!
wenn man von der Ordnung n spricht, weiß man noch nicht, WIE lang der algorithmus wirklich braucht. Das kann man nämlich meist gar nicht effektiv angeben, weil es doch sehr von der Hardware des Rechners abhängt. Man weiß nur, daß der Rechner für die doppelten Daten auch doppelt so lange braucht.
Um zu wissen, wie lang ein Rechner tatsächlich braucht, mußt du wissen, wie lange er für einen Datensatz braucht, die Formel ist
$t=a*n_$
Im linearen Fall weißt du, daß gilt:
$5ms=a*100_$
Du kannst das a berechnen, und dann die Zeit für beliebige n angeben. (Naja, das ist simpler Dreisatz, das merkst du vermutlich gar nicht mal mehr)
Jetzt [mm] n^2 [/mm] :
[mm] $t=a*n^2$
[/mm]
und gegeben ist:
[mm] $5ms=a*100^2$ [/mm] also ist [mm] a=\frac{5ms}{100^2}
[/mm]
und nun:
[mm] $t=a*200^2=a*2^2*100^2=\frac{5ms}{100^2}*2^2*100^2=5ms*4=20ms$
[/mm]
Klar so weit? Kommst du dann mit den letzten beiden auch klar?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:22 Do 30.06.2011 | | Autor: | JBourne |
Danke schon mal! 
Mit n und [mm] n^{2} [/mm] komme ich jetzt zurecht, komme jetzt auch auf dasselbe wie meine Professorin.
Aber mit [mm] log_{2}n [/mm] und n [mm] log_{2}n [/mm] habe ich immer noch Probleme.
Wenn ich mit deinem Ansatz rechne, komme ich nie auf das richtige Ergebnis :-(
|
|
|
| |
|
Dann zeig mal, was du dazu gemacht hast.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:12 Do 30.06.2011 | | Autor: | JBourne |
5ms = a * 100 [mm] log_{2}(100)
[/mm]
a = [mm] \bruch{5ms}{100 log_{2} 100} [/mm]
t = a * 200 [mm] log_{2} [/mm] (200)
t= [mm] \bruch{5}{100 log_{2} 100} [/mm] * 200 [mm] log_{2}(200) [/mm] = 11,5 ms
|
|
|
| |
|
Hallo!
Hmmm, das ist korrekt gerechnet, ich komme aufs gleiche. Und was SOLL da raus kommen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:18 Fr 01.07.2011 | | Autor: | JBourne |
Hallo,
laut meiner Professorin soll es
bei n = 100 t = 5 ms
n = 200 t = 20 ms
n = 400 t = 40 ms
n = 800 t = 80 ms
sein.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:32 Sa 02.07.2011 | | Autor: | felixf |
Moin,
> laut meiner Professorin soll es
>
> bei n = 100 t = 5 ms
> n = 200 t = 20 ms
> n = 400 t = 40 ms
> n = 800 t = 80 ms
> sein.
ich weiss nicht wie sie auf die Zahlen gekommen ist. Die Funktion sieht ziemlich genau linear aus, wenn man den ersten Funktionswert mal ignoriert.
Ich habe beim Nachrechnen auch deine Werte herausbekommen. Und selbst wenn man einen Ansatz der Form $f(n) = [mm] \alpha [/mm] n [mm] \log_2(n) [/mm] + [mm] \beta$ [/mm] oder sogar $f(n) = [mm] \alpha [/mm] n [mm] \log_2(n [/mm] + [mm] \gamma) [/mm] + [mm] \beta$ [/mm] macht, bekommt man nie mehr Werte hin als man Parameter hat.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:45 Sa 02.07.2011 | | Autor: | JBourne |
Welche Werte meinen Sie?
11,5ms ?
Danke,
JBourne
> Moin,
>
> > laut meiner Professorin soll es
> >
> > bei n = 100 t = 5 ms
> > n = 200 t = 20 ms
> > n = 400 t = 40 ms
> > n = 800 t = 80 ms
> > sein.
>
> ich weiss nicht wie sie auf die Zahlen gekommen ist. Die
> Funktion sieht ziemlich genau linear aus, wenn man den
> ersten Funktionswert mal ignoriert.
>
> Ich habe beim Nachrechnen auch deine Werte herausbekommen.
> Und selbst wenn man einen Ansatz der Form [mm]f(n) = \alpha n \log_2(n) + \beta[/mm]
> oder sogar [mm]f(n) = \alpha n \log_2(n + \gamma) + \beta[/mm]
> macht, bekommt man nie mehr Werte hin als man Parameter
> hat.
>
> LG Felix
>
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:27 Sa 02.07.2011 | | Autor: | felixf |
Moin!
> Welche Werte meinen Sie?
> 11,5ms ?
Ja, den Wert mein ich.
LG Felix
|
|
|
|
