[DSAL] Was ist O(|E|)???

[zorgblaubaer]

bei der O-Notation geht es ja im Grunde nur um das asymptotische Verhalten, also muss es nicht für beliebige Werte gelten, insebsondere nicht für 1, sondern nur für wirklich große bzw wie du richtig sagst ab einem bestimmten Initialwert (n0)...

[aRo]

hmm..irgendwie bin ich doch wieder ein wenig wegen dieser O-Notation verwirrt.

Was ist denn der genaue Unterschied zwischen O(|V|) und O(V)?

[Robert]

Was ist denn der genaue Unterschied zwischen O(|V|) und O(V)?

Gar kein Unterschied.
Folie 1323

Konvention: Ist keine Verwechslung zu
befürchten, so bezeichnen wir die Zahl
#V der Knoten bzw. #E der Kanten
einfach mit V bzw. E

[mirko]

hmm..irgendwie bin ich doch wieder ein wenig wegen dieser O-Notation verwirrt.

Was ist denn der genaue Unterschied zwischen O(|V|) und O(V)?

der unterschied ist, dass O(|V|) richtig, und O(V) mathematisch vollkommener blödsinn ist - nur wer zu faul ist, die zwei striche dahin zu malen, der definiert sich halt eine "konvention"

[aRo]

dankeschön, ich kam auch einfach auf keinen Unterschied

[Commo]

Es steht aber auch explizit auf einer der Folien: Konvention: Ist keine Verwechslung zu befürchten, so bezeichnen wir die Zahl #V der Knoten bzw. #E der Kanten einfach mit V bzw. E

[aRo]

ja, danke, aber das steht diesmal 3 Beiträge ÜBER dir...

[Commo]

Alles klar danke^^

[aRo]

ich habe da mal wieder ne ähnliche Frage, selbe Probeklausur.

Zu n Knoten gibt es O(n²) mögliche ungerichtete Graphen.

Meine Antwort:
Ja. Denn es gibt m=n(n-1)/2 mögliche Kanten. Die Graphen können sich nur in der Anzahl der Kanten unterscheiden und das sind eben
m = (n²-n)0.5 viele, was doch in O(n²) liegt.

Wo ist mein Denkfehler? (denn die richtige Antwort ist anscheinend nein..).

[TheStranger]

Du hast recht, dass es O(n^2) viele Kanten gibt. Doch denke, es gibt eine Menge mehr Graphen, denn du kannst die Kanten ja beliebig weglassen.

Bsp: Du hast nen vollständigen Graphen und lässt dann eine Kante weg. Dann hast du schon |E| Graphen (wenn |E| Anzahl Kanten im vollständigen Graphen), wenn du nur eine Kante weglässt. Und das ganze kannst du dann auch mit 2 Kanten weglassen etc spieln.

Gibts bestimmt ne kombinatorische Erklärung für mit tollen Permutationen, doch die will mir grad net einfallen. Ach genau, was wichtig ist, diese Anzahl an Möglichkeiten, wie du Kanten weglassen kannst, wächst mit dem n, d.h. da lässt sich kein konstanter Faktor finden, mit dem du die O Notation abspeisen könntest.

[Commo]

Genau und das wäre dann (n über 2) für gerichtete und ( (n(n+1)/2) über 2) für ungerichtete, weil das alle Kombinationen über {0,1} sind, also die Kante ist enthalten oder nicht. n(n-1)/2 hat man, wenn man Kanten "auf sich selbst" verbietet.