die Komplexitaet der angegebenen Operationen im O-Kalkuel |
know
Grünschnabel
Dabei seit: 21.12.2015
Beiträge: 1
|
|
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
|
|
21.12.2015 10:15 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Kannst Du die erste Frage mit eigenen Worten wiedergeben?
|
|
21.12.2015 10:41 |
|
|
Abed
Mitglied
Dabei seit: 31.10.2015
Beiträge: 27
|
|
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
|
|
21.12.2015 17:20 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
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?
|
|
21.12.2015 21:29 |
|
|
abed1452 unregistriert
|
|
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
|
|
27.12.2015 00:33 |
|
|
Abed
Mitglied
Dabei seit: 31.10.2015
Beiträge: 27
|
|
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)
|
|
27.12.2015 00:46 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Es tut mir leid, aber ich verstehe Dich nicht wirklich. Mir ist nicht klar ob Du die Aufgabenstellung verstehst oder nicht, deswegen kann ich Dir nicht helfen.
|
|
27.12.2015 03:22 |
|
|
Abed
Mitglied
Dabei seit: 31.10.2015
Beiträge: 27
|
|
hmmm okey
trotzdem danke
kannst Du bitte die Frage loeschen
|
|
27.12.2015 13:14 |
|
|
|