Sie sind nicht angemeldet.

perl

Praktikant

  • »perl« ist männlich
  • »perl« ist der Autor dieses Themas

Beiträge: 11

Registrierungsdatum: 29.11.2006

Wohnort: Hannover

Beruf: Informatik-Student

1

14.03.2007, 18:45

DuA Folien Laufzeiten

Hallo!
Ich stecke grade in der Vorbereitung für die Datenstrukturen und Algorithmen Klausur und habe mich über die Laufzeitangaben eines ADT Set, durch einfach verkettete Listen implementiert, gewundert. (Folienskript, Seite 183)

Da ist für size() (= Mächtigkeit der Menge), add(e) (= Element in Menge einfügen) und union(m, n) (= Schnittmenge von zwei Mengen) jedes Mal konstante Laufzeit angegeben. Implementiert wird das ganze durch einfach verkettete Listen, Elemente unsortiert, mit Zeiger auf erstes und letztes Element.

Zu size():
Um herauszufinden, wieviele Elemente nun in der Menge stecken, muss ich doch die Liste von Anfang bis Ende durchgehen und einen Zähler mitlaufen lassen, oder? Ein Zeiger auf's Ende nützt mir doch hier nichts. Nach meinem Verständnis wäre das also nur in O(n) zu schaffen.

Zu add(e):
Bevor ich ein Element hinzufügen kann, muss ich doch erst einmal schauen, ob es nicht vielleicht schon Element der Menge ist, oder? Und contains() ist mit einer Laufzeit von O(n) angegeben.

Zu union(m, n):
Da muss doch quasi jedes Element aus der ersten Menge in die zweite Einfügen. Damit hätte auch dieser Algorithmus eine Laufzeit von O(M * N), wie auch intersection() und difference().

Kurz gesagt werde ich aus den Angaben nicht schlau. Kann es sein, dass ich da irgendwelche Grundannahmen übersehen habe, so dass die Funktionen doch bessere Laufzeit haben?

Ich hoffe, ihr könnt mir helfen.

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

14.03.2007, 20:10

RE: DuA Folien Laufzeiten

Zitat

Original von perl
Zu size():
Um herauszufinden, wieviele Elemente nun in der Menge stecken, muss ich doch die Liste von Anfang bis Ende durchgehen und einen Zähler mitlaufen lassen, oder? Ein Zeiger auf's Ende nützt mir doch hier nichts. Nach meinem Verständnis wäre das also nur in O(n) zu schaffen.
Wenn man zusätzlich zu der Liste noch eine Variable speichert, die die Größe der Liste beinhaltet, ist size() in O(1) machbar.

Bei add und union sehe ich dieselben Probleme wie Du.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

BLUESCREEN

Junior Schreiberling

  • »BLUESCREEN« ist männlich

Beiträge: 244

Registrierungsdatum: 11.10.2005

3

14.03.2007, 20:45

Im Skript steht auf Seite 61, dass insert() und union() bei dieser Implementation mehrfach auftretende Elemente erlauben.
Eine Vereinigung (union()) von zwei Mengen würde dann aber dazu führen, dass beide Mengen sich die selben Daten teilen ...
edit: Außerdem würde nicht die Vereinigung zurückgegeben werden, sondern die eine Menge verändert werden, was ein Gegenspruch zu Seite 60 ist.

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »BLUESCREEN« (14.03.2007, 20:53)


Currywurst mit Pommes

Erfahrener Schreiberling

Beiträge: 438

Registrierungsdatum: 14.10.2002

4

15.03.2007, 08:18

Ich glaube fast, ADT Set wird nicht dran kommen. Das Skript enthält da doch recht viele "Bugs". Die Bitvektor-Implementierung ist z.B. auch nicht sehr stimmig.

Zu size: Geht man nach Skript ADT Liste (Verkettet), so müsste size O(N) sein. Aber wie Joachim schon sagte, es ist auch in O(1) möglich. Müsste man wohl evtl. in der Klausur vorsichtshalber erläutern...

Zu add(e): Man könnte wohl auch ohne Überprüfung einfach Elemente mehrfach einfügen. Das geht allerdings zu Lasten des Speichers und erscheint doch sehr unsinnig. Bei remove(e) müsste dann alle (mehrfach vorhandenen) Elemente entfernt werden. Dann wäre add: O(1) und remove O(n).

neon

Praktikant

  • »neon« ist männlich

Beiträge: 11

Registrierungsdatum: 15.03.2007

5

15.03.2007, 12:34

Ich habe ein kleines Problem mit der Aufgabe 1 b) der Übungsklausur.

Handelt es sich nicht hierbei um eine Endlosschleife? Falls ja, wie gebe ich die Laufzeit an und begründe das?

Für Hilfe wäre ich dankbar!

Currywurst mit Pommes

Erfahrener Schreiberling

Beiträge: 438

Registrierungsdatum: 14.10.2002

6

15.03.2007, 16:44

Zitat

Original von neon
Ich habe ein kleines Problem mit der Aufgabe 1 b) der Übungsklausur.


Meine Gedanken dazu gabs in diesem Thread:

http://forum.finf.uni-hannover.de/thread.php?threadid=5551

perl

Praktikant

  • »perl« ist männlich
  • »perl« ist der Autor dieses Themas

Beiträge: 11

Registrierungsdatum: 29.11.2006

Wohnort: Hannover

Beruf: Informatik-Student

7

15.03.2007, 21:58

Zitat

Original von neon
Ich habe ein kleines Problem mit der Aufgabe 1 b) der Übungsklausur.

Handelt es sich nicht hierbei um eine Endlosschleife? Falls ja, wie gebe ich die Laufzeit an und begründe das?

Für Hilfe wäre ich dankbar!


Tz tz tz, nennt man sowas nicht Thread-Hijacking?

neon

Praktikant

  • »neon« ist männlich

Beiträge: 11

Registrierungsdatum: 15.03.2007

8

16.03.2007, 08:53

Zitat

Original von Currywurst mit Pommes

Zitat

Original von neon
Ich habe ein kleines Problem mit der Aufgabe 1 b) der Übungsklausur.


Meine Gedanken dazu gabs in diesem Thread:

http://forum.finf.uni-hannover.de/thread.php?threadid=5551


Schön, aber wie kommst du darauf? Mir hat die whileschleife probleme gemacht. n*n ist mir klar aber log(n)?

Currywurst mit Pommes

Erfahrener Schreiberling

Beiträge: 438

Registrierungsdatum: 14.10.2002

9

16.03.2007, 09:42

Es hat ja noch keiner darauf geantwortet, ob es richtig ist...aber:

k = n
Dann wird k immer durch 4 geteilt bist k = 0 ist. k ist ja ein integer, 1/4 müsste also null ergeben.

Bei n = 4 wäre das 1 (+1) mal
Bei n = 16 wäre das 2 (+1) mal
Bei n = 64 wäre das 3 (+1) mal
Bei n = 256 wäre das 4 (+1) mal
...

Läuft also im Endeeffekt auf log4(n) raus

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Currywurst mit Pommes« (16.03.2007, 09:43)


np

Junior Schreiberling

Beiträge: 155

Registrierungsdatum: 23.10.2002

10

21.03.2007, 10:02

Zitat

Original von Currywurst mit Pommes
Es hat ja noch keiner darauf geantwortet, ob es richtig ist...aber:
Ist richtig.

Zu den "Bugs" bzgl. des ADT Set hatte ich mich in der Vorlesung ja ausführlich geäußert. Kurzfassung: Es hängt immer davon ab, was man in der Anwendung will. Schnelle Laufzeiten -> evtl. doppelte Elemente
Außerdem hatte ich ja erwähnt, dass ich mit den Folien teilweise etwas unzufrieden bin, da hier einige Sachverhalte zu stark verkürzt werden. Wer jedoch ausschließlich nach den Folien lernt, ohne je in der Vorlesung oder Übung gewesen zu sein (und dieser Verdacht beschleicht mich angesichts so mancher Nachfrage), der ist selbst Schuld.

Allen anderen wünsche ich noch viel Erfolg beim Lernen. Keine Angst, es wird schon nicht so schlimm!

Niklas Peinecke

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »np« (21.03.2007, 10:02)


Currywurst mit Pommes

Erfahrener Schreiberling

Beiträge: 438

Registrierungsdatum: 14.10.2002

11

21.03.2007, 10:43

Hat jemand noch eine Idee für folgende Aufgabe der Übungsklausur:

Gegeben seien zwei Heaps. Schlagen Sie einen Algorithmus vor, der in O(logN) (mit N als Gesamtzahl der Knoten) diese zu einem binären Baum mit Heap-Eigenschaft zusammensetzt! Beachten Sie, dass dieser resultierende Baum nicht fast vollständig sein muss.

Mir mag kein O(logN) Algorithmus einfallen....

DrChaotica

Senior Schreiberling

  • »DrChaotica« ist männlich

Beiträge: 714

Registrierungsdatum: 22.01.2005

Wohnort: SHG

Beruf: SW-Entwickler

12

21.03.2007, 11:20

Also quasi aus zwei Heaps einen einzigen (Beinahe-Heap, da Vollständigkeitseigenschaft nicht erfüllt)-Tree machen? Mhh, dann überleg mal was du in Zeit O(log n) machen kannst...nicht einmal die Zeit, um alle Elemente anschauen zu können bleibt dir. Also musst du wohl größere Teile unangesehen in die neue Struktur einfügen...

Das log(n) kommt auch nicht von ungefähr, es ist eigentlich schon ein ziemlich grosser Hinweis zur Lösung dieser Aufgabe, sonst hätte man ja auch schreiben können: machen Sie es besser als in O(n), oder so. Und besonders viel Zeit, um in einer Klausur einen eigenen log(n)-Algorithmus zu beschreiben hat man normalerweise nicht sehr oft...

Denk naheliegend, und versuche Heap-Algorithmen zu benutzen, um dieses Problem zu lösen...

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »DrChaotica« (21.03.2007, 11:25)


Currywurst mit Pommes

Erfahrener Schreiberling

Beiträge: 438

Registrierungsdatum: 14.10.2002

13

21.03.2007, 12:33

Ich dachte auch erst, es wäre einfach...aber irgendwie hab ich wohl einen Denkfehler.

siftUp/Down wären in O(logN) möglich. Aber wieviele Knoten ich siften muss, hängt vom Heap ab.

Quellcode

1
2
3
4
5
6
7
8
9
         50
   6            20
1    3        8     9


und

        60
    2       4


Wie soll ich den unteren Heap in log(N) einfügen...? Komm nicht drauf. Einen Knoten kann ich in O(log(N)) an die richtige Position siften. Aber die anderen Beiden müssen ja auch an die richtige Position.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Currywurst mit Pommes« (21.03.2007, 12:36)


Currywurst mit Pommes

Erfahrener Schreiberling

Beiträge: 438

Registrierungsdatum: 14.10.2002

14

21.03.2007, 12:37

Ah ! jetzt hab ichs :) Ich lege die beiden Heaps nebeneinander und als Wurzelknoten, der Kanten zu beiden Heaps hat, füge ich den letzten Knoten aus Heap A oder B ein. Dann siftDown.

Toll...in der Klausur wäre das nix geworden. Naja :).

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Currywurst mit Pommes« (21.03.2007, 12:39)


neon

Praktikant

  • »neon« ist männlich

Beiträge: 11

Registrierungsdatum: 15.03.2007

15

21.03.2007, 13:35

Nur zur Kontrolle:

Probeklausur Aufgabe 3 b)


Postordnung mit Verzweigungsgrad

5 3 sin * cos 8 15 2 + * +

0 0 1 2 1 0 0 0 2 2 2

Ist das richtig?

Wie würdet ihr zu 3 c) antworten?

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »neon« (21.03.2007, 13:47)


Scooby22

Trainee

  • »Scooby22« ist männlich

Beiträge: 77

Registrierungsdatum: 12.09.2004

Wohnort: Laatzen

Beruf: Angew. Informatik

16

21.03.2007, 14:15

5 3 sin * cos 8 15 2 + * +

0 0 1 2 1 0 0 0 2 2 2

Bin mir eigentlich ziemlich sicher .

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »Scooby22« (21.03.2007, 14:20)


Currywurst mit Pommes

Erfahrener Schreiberling

Beiträge: 438

Registrierungsdatum: 14.10.2002

17

21.03.2007, 14:42

Zitat

Wie würdet ihr zu 3 c) antworten?


So wie es im Skript (main.pdf) steht :)