Komplexität < Algorithm. Geometrie < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:29 Fr 21.07.2006 | | Autor: | Bastiane |
Hallo schon wieder! 
Erstmal eine etwas allgemeinere Frage:
Wenn es heißt, "etwas hat die Komplexität sowieso", dann geht es quasi um die Anzahl der Ecken und Kanten oder so und nicht um die Komplexität des Algorithmus, den man nimmt, um etwas aufzubauen oder so!?
Falls die Frage nicht ganz klar ist, wird sie wahrscheinlich klar, wenn ihr euch ![[]](/images/popup.gif) das hier mal anschaut. Davon handelt nämlich auch meine eigentliche Frage. Und zwar steht dort: "da der Sichtbarkeitsgraph selber mindestens [mm] O(n^2) [/mm] hat". Die beiden Beispiele sind mir klar, allerdings habe ich Probleme mit dem O. Bei mir im Skript steht, dass der Sichtbarkeitsgraph die Komplexität [mm] \Omega(n^2) [/mm] hat. Ist das ein Druckfehler? Oder ist das in diesem Fall dasselbe? Also ich habe das immer so verstanden, dass [mm] \Omega [/mm] doch eine untere Schranke ist. Und wenn es doch Beispiele gibt, wo es weniger Kanten sind, dann kann doch [mm] n^2 [/mm] keine untere Schranke sein, oder? [mm] O(n^2) [/mm] würde hier meiner Meinung nach viel mehr Sinn machen, denn mehr als [mm] n^2 [/mm] kann es ja nicht geben, weil dann schon jedes mit jedem verbunden ist. Allerdings verstehe ich dann nicht, warum dort steht "mindestens [mm] O(n^2)"!? [/mm] ![[kopfkratz]](/images/smileys/kopfkratz.gif "[kopfkratz]")
Irgendwie bekomme ich das mit dem O und dem [mm] \Omega [/mm] nicht in meinen Kopf hinein. ![[haee]](/images/smileys/haee.gif "[haee]")
Vielleicht kann mir das ja nochmal jemand erklären.
viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:22 So 23.07.2006 | | Autor: | sylle82 |
Die Komplexität eines Algorithmus beschreibt meines Erachtens die Anzahl der nötigen Operationen (oder Schritte) wie Multiplikation, Division oder Vergleiche, die nötig sind, um eine Aufgabe zu lösen.
Dabei ist $ O $ die obere Schranke (ein Algorithmus braucht bestimmt nicht mehr Schritte als dort angegeben) und $ [mm] \Omega [/mm] $ die untere Schranke für die Komplexität.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:52 Mi 02.08.2006 | | Autor: | Bastiane |
Hallo!
> Die Komplexität eines Algorithmus beschreibt meines
> Erachtens die Anzahl der nötigen Operationen (oder
> Schritte) wie Multiplikation, Division oder Vergleiche, die
> nötig sind, um eine Aufgabe zu lösen.
Ja, aber wieso hat denn dann ein Sichtbarkeitsgraph eine Komplexität? Es geht ja nicht um die Komplexität eines Algorithmus um diesen zu berechnen, sondern um die Komplexität des Graphen selber!
> Dabei ist [mm]O[/mm] die obere Schranke (ein Algorithmus braucht
> bestimmt nicht mehr Schritte als dort angegeben) und [mm]\Omega[/mm]
> die untere Schranke für die Komplexität.
Ja, genau. Aber wieso kann dann [mm] \Omega(n^2) [/mm] eine untere Schranke sein, wenn es ein Beispiel dafür gibt, dass nur O(n) viele Kanten hat???
Kann mir das niemand erklären?
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:31 Di 08.08.2006 | | Autor: | mathiash |
Liebe Bastiane,
die untere Schranke [mm] \Omega [/mm] ( [mm] n^2)
[/mm]
bedeutet nicht, dass jeder Sichtbarkeitsgraph so gross ist, sondern dass es eine Konstante c gibt, so dass fuer unendlich viele Werte von n
ein Beispiel existiert, bei dem der Sichtbarkeitsgraph mindestens Groesse [mm] c\cdot n^2 [/mm] hat.
Das heisst dann uebrigens ja auch, dass jeder Algorithmus, der den Sichtbarkeitsgraphen komplett erzeugt (Lista von Knoten und Kanten zB),
mindestens soviele Schritte braucht.
Gruss,
Mathias
|
|
|
|
