Komplexität einfügen in verkettete Liste (von: Datenstrukturen)

Also die Laufzeit is inner O-Notation für n Einfüge-Operationen O(n*n). Das kann man noch weiter differenzieren, je nach dem, ob du zusätzlich zu dem Anfang noch weitere Zeiger speicherst, oder net...
Wenn nur der Anfang gespeichert wird, dann
1. Element einfügen: 1,5*1=1.
2. Element einfügen: 1,5*2=3.
3. Element einfügen: 1,5*3=4.
4. Element einfügen: 1,5*4=6.
5. Element einfügen: 1,5*5=7.
6. Element einfügen: 1,5*6=9.
Usw.
1+3+4+6+7+9=30. 6*x=30<=>x=5=n-1.
1+3+4+6+7+9+10+12+13+15=80. 10*x=80<=>x=8=n-2.
1+3+4+6+7+9+10+12+13+15+16+18=114. 12*x=114<=>x=9,5=n-2,5.
=>Die genau Laufzeit wäre also n*n*(n*0,8/n). (?)
 
Es wird aber natürlich die Einfügeoperation an sich betrachtet und n ist nicht die Anzahl der Einzufügenden Elemente!

Somit hätte man eine Operation O(n) und nicht O(n^2).

Erkennt man auch bei Deiner Zahlenreihe: verdoppelte Anzahl an Elementen verdoppelte den Aufwand => linearer Anstieg und nicht Quadratisch.

Siehe z.B. www.saar.de/~awa/ONotation.html für Erläuterungen zur O Notation.
 
Nein, Bitte verstehe erst die O-Notation, bevor Du mit mir diskutieren möchtest... Danke.

Bearbeitung:
Wenn n Elemente in ein Array einfügst, dann sind das ja auch n mal konstanter Aufwand und damit O(n) so man Deiner Logik folgen möchte
Seit wann ist denn n*n konstanter oder linearer Aufwand? ...

Mein Gott, das sind starke Mathematik-Grundlagen-Defizite... Aber ne... schon vergessen, ich bin ja der der trollt... :rolleyes:
 
Zuletzt bearbeitet:
n ist natürlich die Anzahl der einzufügenden Elemente insgesamt.
Nein, n ist die Länge der Liste bzw. des Arrays. Siehe Aufgabenstellung im Eröffnungsposting:
Ich habe ein Array A und eine einfach verkettete Liste ungerader Länge n (gegeben für das Array, noch unbekannt für die Liste). Ich soll auf das Element in der Mitte zugreifen und feststellen, wie viele Elemente ich besuchen muss, um darauf zugreifen zu können
 
Nein, n ist die Länge der Liste bzw. des Arrays. Siehe Aufgabenstellung im Eröffnungsposting:
Wobei das egal ist, denn es geht bei der O-Notation ja nicht um die Frage nach einem konkreten Aufwand bei n Elementen in der Liste. O(n) ist eine Menge bei der die Komplexität n, 1,5*n, n+7 u.s.w enthalten wäre.

Daher ist das etwas, das über die Fragestellung des TE hinaus geht. Aber Fakt ist: es wird eine Funktion bewertet (Hier einfügen in die Liste) und n bezeichnet dabei auch die Anzahl der Elemente und es geht um die Komplexität eines Durchgangs ....
 
Es gibt mehrere Definitionen für n... Ich habe in diesem Zusammenhang eine naheliegende gewählt.
Du hast aber doch die O-Notation verwendet. Und diese ist klar definiert. Oder sollte es die Tobias-nrw Notation gewesen sein, für die Du auch eine Notation wie bei der O-Notation verwendet hast? Dann definier Deine Notation bitte, ehe du diese verwendest.
 
Können wir uns nicht darauf verständigen, alle "Beleidigungen" zu unterlassen?
Wo bitte war das eine Beleidigung? Wenn du die O-Notation verwendest, dann sollte es die O-Notation sein. Du kannst gerne eine andere Notation verwenden, aber das ist dann nicht die O-Notation. Und Namensgebung ist oft, dass einfach der Erfinder genommen wird. Oder ist es eine Beleidigung, dass man z.B. von Heisenbergs Unschärferelation spricht?

Und wenn du meinen Links gefolgt wärst, dann hättest du auch klar gelesen, dass es eben um Funktionen und nicht Programme geht... Und das PDF des zweiten Links definiert auch noch mehr Notationen (Seite 20ff). Da hätten wir z.B. eine Grundlage auf der man diskutieren könnte.
 
Seit wann ist denn n*n konstanter oder linearer Aufwand? ...

Mein Gott, das sind starke Mathematik-Grundlagen-Defizite... Aber ne... schon vergessen, ich bin ja der der trollt... :rolleyes:
Ich finde es interessant, dass Du sowas vom Stapel lässt und dann bei einfachen Aussagen Dich beleidigt fühlst.
Bitte lies und versteh, ehe du antwortest. Ich habe klar von einfügen in ein Array geschrieben. Das hat was für eine O-Notation?

Ich habe Dir schon einmal geschrieben, was Kommunikation beinhaltet. Wenn Du nicht bereit bist, den Gegenüber zu verstehen, dann ist es keine Kommunikation. Das ist evtl. Selbstdarstellung.

Und Argumente suche ich derzeit vergeblich bei Dir....
 
Es gibt kein Gesetz, neben den Kosten für die Einzeloperationen nicht auch die Gesamtkosten in der O-Notation anzugeben. (Das ist bei Algorithmen ja auch allgemein der Fall.)

Eine Beleidigung des Erfinders selbiger kann ich nicht erkennen.

Das sind alles unterschwellige (arglistige) Unterstellungen, womit Du mich viell provozieren willst...
 
Zuletzt bearbeitet:
Ich will Dich in keiner Weise provozieren. Wenn fachliche Richtigstellungen für Dich aber eine Provokation sind, dann solltest Du Deine Aussagen besser prüfen oder schlicht seien lassen. Oder es einfach so machen wie andere auch: Mit sachlichen Argumenten reagieren.
Und bei O(n) steht n nicht für eine Anzahl an Operationen. Wenn du sowas betrachten möchtest, dann wäre es - wie von jemand anderen geschrieben - maximal O(n*m) oder so, wobei das evtl. eher auch m*O(n) hinaus laufen würde. Bei einem fix vorgegebenen m wäre das aber wieder eine Komplexität O(n) fürchte ich. Könnte man alles genauer definieren und betrachten. Hier haben wir aber lediglich einen Algorithmus, den wir betrachten und dieser hat eine gewisse Komplexitätsklasse. Diese kann man angeben, wozu die O-Notation da ist.

wenn du etwas anderes machen willst, musst du dies genauer definieren und erläutern. Die reine O-Notation scheinst du aber nicht korrekt angewendet zu haben.
 
Passende Stellenanzeigen aus deiner Region:

Oben