O Notaion eines Algorithmus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Gegeben sind folgende Algorithmen, bestimmen Sie die O-Notation:
a) for (int i=0; i<=n; i++) sum++;
b) for (int i=0; i<=n; i++)
for (int j=0; j<=2*n; j++)
write (i+ " " +j);
|
Hallo,
könnte mir jemand sagen ob das hier richtig ist?
a) n-mal for Schleife= z+v
n-mal sum++ = z
ergibt: n*(2*z+v) = O(n)
b) n-mal erste for Schleife= z+v
2n-mal zweite for Schleife= z+v
2n-mal ausgabe=0
ergibt: n*((z+v)+2*n*(z+v+s))
= [mm] n*(z+v)*2n^2*(z+v+s)
[/mm]
= [mm] O(n^2)
[/mm]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:31 So 28.01.2007 | | Autor: | stovi0040 |
Also das stimmt so wie du es gelöst hast!
a) ist Lösung durch hinschauen!
b) zwei geschachtelte Schleifen = n * 2n = [mm] O(n^2)
[/mm]
mfg stovi0040
|
|
|
|
