O Notation Algorithmus
Neue Frage »

29.10.2010, 18:11 mathe23 Auf diesen Beitrag antworten »
O Notation Algorithmus
Hi,

ich habe eine Klasse die bei der Konstruktuion folgendes macht:

1. Methode A wird aufgerufen mit einer Foreach Schleife über N Elemente
2. Methode B wird aufgerufen mit einer Foreach Schleife über N Elemente

=> n + n => 2n => O(n) ?

oder

=> O(2n) ?

Ich habe folgendes PDF gefunden:
http://www.fmi.uni-stuttgart.de/fk/mensc...Informatik2.pdf

Die Regel von l'Hospital ist mir bekannt, ableiten kann ich auch...

Vielen Dank schonmal
29.10.2010, 19:58 gitterrost4 Auf diesen Beitrag antworten »
RE: O Notation Algorithmus
Du kannst sehr leicht nachpruefen, dass

O(n)=O(2n)

ist. Dies wuerde ich an deiner Stelle einmal tun.

Weiterhin ist die Frage: Laufen die Methoden A und B mit konstanter Laufzeit?
29.10.2010, 20:07 mathe23 Auf diesen Beitrag antworten »

Ich kann nicht ganz folgen?

Die Schleifen laufen mit konstanter Geschwindigkeit.
29.10.2010, 20:25 Abakus Auf diesen Beitrag antworten »
RE: O Notation Algorithmus
Hallo!

Wenn du dir die Definition der Landau-Symbole anschaust, wirst du schnell feststellen:



Versuche zB zu beweisen.

Grüße Abakus smile

edit: viel zu spät, @ gitterrost4: du darfst gerne weitermachen
29.10.2010, 20:34 mathe23 Auf diesen Beitrag antworten »

Folglich kann die sagen die Klasse ist in ihrem Verhalten O(n) ?

Ich meine wenn ich sage O(2n) dann könnte man evtl vermuten 2 Schleifen. Bei O(n) denkt jeder direkt an eine Schleife.
29.10.2010, 20:37 gitterrost4 Auf diesen Beitrag antworten »

Es ist eigentlich voellig egal, ob du sagst, die Klasse laufe in O(n) oder O(2n) da gibt es nichts hineinzuinterpretieren. Konvention ist es allerdings konstante Faktoren (also hier die 2) eher wegzulassen.
 Anzeige 
 
29.10.2010, 21:18 mathe23 Auf diesen Beitrag antworten »

Ok,

Betrachten wir folgenden Code.

php: 
1:
2:
3:
4:
5:
6:
7:
8:

foreach($base as $str) {

if($hash[$str] != null) //oder isset was auch immer
$hash[$str] += 1;
else
$hash[$str] = 1;

}


Die Operation $hash[$i] (Zugriff) ist O(n). Die Zuweisung $hash[$str] = $x ist ebenfalls O(n).

Wie ist O dieser Schleife?

Die Schleife zählt quasi wie oft ein Wert in $base vorhanden ist. => $hash wird größer.
29.10.2010, 21:24 gitterrost4 Auf diesen Beitrag antworten »

Selbst irgendwelche Ideen? Zaehl einfach mal durch, wie viele Operationen ausgefuehrt werden.
29.10.2010, 21:29 mathe23 Auf diesen Beitrag antworten »

1Vergleich und 1Keyabfrage //if
dann jeweils 1Operation

Hm...
29.10.2010, 21:35 gitterrost4 Auf diesen Beitrag antworten »

Naja du sagtest ja aber, dass hash[$i] in O(n) laeuft. Also hast du dann ja in jedem Schleifendurchlauf 3n Operationen. Wieviel macht das dann insgesamt?
29.10.2010, 21:39 mathe23 Auf diesen Beitrag antworten »

Achso ich wußte nicht das man eine Operation die O(n) ist dann einfach + 1n dazu zählen darf Forum Kloppe

=> O(n) ?
29.10.2010, 21:46 gitterrost4 Auf diesen Beitrag antworten »

Nicht ganz.

Sei m die Laenge von $base. Dann laeuft jeder Schleifendurchlauf in O(n). Du hast m Schleifendurchlaeufe. Also liegst du in O(n*m)
29.10.2010, 21:52 mathe23 Auf diesen Beitrag antworten »

Ah das ist logisch...

anzahl=3 dann wäre ja n + n + n

=> 3 = dein m deswegen O(n*m)

Ok danke!
29.10.2010, 22:08 mathe23 Auf diesen Beitrag antworten »

Wenn jetzt in der Schleife eine Methode aufgerufen wird die O(n²) wäre wurden dann folgen => O(n²*m) ?
29.10.2010, 22:13 gitterrost4 Auf diesen Beitrag antworten »

Jap Freude
30.10.2010, 12:14 mathe23 Auf diesen Beitrag antworten »

Wenn ich nun habe

php: 
1:
2:
3:
4:
5:
6:
7:

for($i=0; $i < $n; $i++) {

echo "hi";

echo "hi";

}


=> n(1+1) => 2n => O(n)?
30.10.2010, 12:35 gitterrost4 Auf diesen Beitrag antworten »

Freude
30.10.2010, 13:25 mathe23 Auf diesen Beitrag antworten »

jetzt kann mich nichts mehr aufhalten hahaharghahargh Teufel
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


MatheBoard » Hochschulmathematik » Sonstiges » O Notation Algorithmus