Informatiker Board | Druckvorschau: die Komplexitaet der angegebenen Operationen im O-Kalkuel

Geschrieben von know am 21.12.2015 um 10:15:

die Komplexitaet der angegebenen Operationen im O-Kalkuel

Meine Frage:
Geben Sie die kleinste obere Schranke f ?
ur die Komplexitaet der angegebenen Operationen im
O-Kalkuel an
a) Einfuegen an der Position k < n in eine Listenstruktur von n Elementen, implementiert als:
? Array (unter Erhalt aller bereits existenten Eintrage. Nehmen Sie an, dass am Ende,des Arrays noch leere Eintraege existieren.)
? einfach verkettete Liste
? doppelt verkettete Liste
b) Erweitern der Kapazitaet und anschließendes Einfuegen am Ende einer Listenstruktur beste-
1hend aus n Elementen und einer maximalen Kapazitaet von m = n Elementen, implementiert
als:
? Array
? einfach verkettete Liste
? doppelt verkettete Liste

Meine Ideen:
keine Idee

Geschrieben von ed209 am 21.12.2015 um 10:41:

Kannst Du die erste Frage mit eigenen Worten wiedergeben?

Geschrieben von Abed am 21.12.2015 um 17:20:

ah okey sorry
Geben Sie die kleinste obere Schranke fuer die Komplexitaet der angegebenen Operationen im O-Kalkuel an mit begrundung
a) Einfuegen an der Position k < n in eine Listenstruktur von n Elementen, implementiert als:
Array (unter Erhalt aller bereits existenten Eintrage. Nehmen Sie an, dass am Ende,des Arrays noch leere Eintraege existieren.)?
.einfach verkettete Liste
.doppelt verkettete Liste
b) Erweitern der Kapazitaet und anschließendes Einfuegen am Ende einer Listenstruktur beste-
1hend aus n Elementen und einer maximalen Kapazitaet von m = n Elementen, implementiert
als:
. Array
. einfach verkettete Liste
. doppelt verkettete Liste

c) Loeschen des ersten Elements einer Listenstruktur von n Elementen, implementiert als:
• Array (das an jeder Position nur gueltige Elemente enthalten darf!)
• einfach verkettete Liste
• doppelt verkettete Liste
d) Finden des Medians (= mittleres Element in sortierter Reihung) in einer aufsteigend
sortierten Listenstruktur mit n Elementen, implementiert als:
• Array
• einfach verkettete Liste
• doppelt verkettete Liste

Geschrieben von ed209 am 21.12.2015 um 21:29:

Als ich "mit eigenen Worten" schrieb meinte ich eigentlich mit eigenen Worten. Jetzt hast du dasselbe nochmal geschrieben....

Kannst Du es vielleicht nur den ersten Teil der Aufgabe selbst formulieren?

Geschrieben von abed1452 am 27.12.2015 um 00:33:

oh sorry
also die Frage war so ..
Geben Sie die kleinste obere Schranke fuer die Komplexität der angegebenen Operationen im
O-Kalkuel an. Begruenden Sie ihre Antwort fuer jede Operation und jede Datenstruktur kurz

Geschrieben von Abed am 27.12.2015 um 00:46:

eig weiss ich nicht die Frage war so
aber ich glaube
Einfügen eines Element an der SStelle k in einen Array [n]
vorher sollen wir die elemente ,die bereits in der stelle K eingefuegt werden , mit >= k jeweils verschieben
der Aufwand O(n-k)