Laufzeit < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:03 Mo 10.12.2012 | | Autor: | Maurizz |
| Aufgabe | a) Geben Sie die Laufzeit T(n) in Abhängigkeit der Laufzeiten a, b, c der einzelnen Programmteile A, B, C an.
Hinweis: T(n) ist ein Polynom in n.
b) Laufzeitmessungen des gesamten Programms ergaben: für n = 10 bekommt man eine Laufzeit von 148.5 Sekunden, für n = 20 sind es 493.7 Sekunden sowie 1040.9 Sekunden für n = 30. Berechnen Sie daraus die Laufzeiten a,b,c.
Eingabe n 2 N
Programmteil A
für i=1,...,n
{
Programmteil B
für j=1,...,n
{
Programmteil C
}
Programmteil B
} |
a)
A = O(n)
B = O(n) [mm] \Rightarrow [/mm] A*B = [mm] O(n^{2})
[/mm]
C = ? etwa O(1)?
Wenn ich annehme das C jeweils einmal ausgeführt wird,
dann habe ich doch T(n) = [mm] n^{2}
[/mm]
b)
Hier bin ich etwas verwirrt. Ich denke man kann ein LGS aufstellen.
Oder sogar noch einfacher.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:19 Mo 10.12.2012 | | Autor: | link963 |
> a) Geben Sie die Laufzeit T(n) in Abhängigkeit der
> Laufzeiten a, b, c der einzelnen Programmteile A, B, C an.
> Hinweis: T(n) ist ein Polynom in n.
>
> b) Laufzeitmessungen des gesamten Programms ergaben: für n
> = 10 bekommt man eine Laufzeit von 148.5 Sekunden, für n =
> 20 sind es 493.7 Sekunden sowie 1040.9 Sekunden für n =
> 30. Berechnen Sie daraus die Laufzeiten a,b,c.
>
> Eingabe n 2 N
Was ist hier mit "2 N" gemeint ?
> Programmteil A
> für i=1,...,n
> {
> Programmteil B
> für j=1,...,n
> {
> Programmteil C
> }
> Programmteil B
> }
> a)
> A = O(n)
Nein. Die Laufzeit von A ist eigentlich a. A wird einmal ausgeführt im gesamten Programm. Also hast du T = ?
> B = O(n) [mm]\Rightarrow[/mm] A*B = [mm]O(n^{2})[/mm]
Ja. B wird 2*n mal ausgeführt. Schreibe die Laufzeit in Abhängigkeit von b.
> C = ? etwa O(1)?
Nein.
>
> Wenn ich annehme das C jeweils einmal ausgeführt wird,
> dann habe ich doch T(n) = [mm]n^{2}[/mm]
Ja. Also nichts mit O(1). Schreibe auch das in Abhängigkeit von c.
>
> b)
> Hier bin ich etwas verwirrt. Ich denke man kann ein LGS
> aufstellen.
> Oder sogar noch einfacher.
MfG Link963
|
|
|
|
