Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

perl

Praktikant

  • "perl" is male
  • "perl" started this thread

Posts: 11

Date of registration: Nov 29th 2006

Location: Hannover

Occupation: Informatik-Student

1

Wednesday, March 14th 2007, 6:45pm

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.
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Wednesday, March 14th 2007, 8:10pm

RE: DuA Folien Laufzeiten

Quoted

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
  • Send private message

BLUESCREEN

Junior Schreiberling

  • "BLUESCREEN" is male

Posts: 244

Date of registration: Oct 11th 2005

3

Wednesday, March 14th 2007, 8:45pm

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.

This post has been edited 2 times, last edit by "BLUESCREEN" (Mar 14th 2007, 8:53pm)

  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

Posts: 438

Date of registration: Oct 14th 2002

4

Thursday, March 15th 2007, 8:18am

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).
  • Send private message

neon

Praktikant

  • "neon" is male

Posts: 11

Date of registration: Mar 15th 2007

5

Thursday, March 15th 2007, 12:34pm

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!
  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

Posts: 438

Date of registration: Oct 14th 2002

6

Thursday, March 15th 2007, 4:44pm

Quoted

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
  • Send private message

perl

Praktikant

  • "perl" is male
  • "perl" started this thread

Posts: 11

Date of registration: Nov 29th 2006

Location: Hannover

Occupation: Informatik-Student

7

Thursday, March 15th 2007, 9:58pm

Quoted

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?
  • Send private message

neon

Praktikant

  • "neon" is male

Posts: 11

Date of registration: Mar 15th 2007

8

Friday, March 16th 2007, 8:53am

Quoted

Original von Currywurst mit Pommes

Quoted

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)?
  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

Posts: 438

Date of registration: Oct 14th 2002

9

Friday, March 16th 2007, 9:42am

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

This post has been edited 1 times, last edit by "Currywurst mit Pommes" (Mar 16th 2007, 9:43am)

  • Send private message

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

10

Wednesday, March 21st 2007, 10:02am

Quoted

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

This post has been edited 1 times, last edit by "np" (Mar 21st 2007, 10:02am)

  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

Posts: 438

Date of registration: Oct 14th 2002

11

Wednesday, March 21st 2007, 10:43am

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....
  • Send private message

DrChaotica

Senior Schreiberling

  • "DrChaotica" is male

Posts: 714

Date of registration: Jan 22nd 2005

Location: SHG

Occupation: SW-Entwickler

12

Wednesday, March 21st 2007, 11:20am

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...

This post has been edited 1 times, last edit by "DrChaotica" (Mar 21st 2007, 11:25am)

  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

Posts: 438

Date of registration: Oct 14th 2002

13

Wednesday, March 21st 2007, 12:33pm

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.

Source code

 
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.

This post has been edited 1 times, last edit by "Currywurst mit Pommes" (Mar 21st 2007, 12:36pm)

  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

Posts: 438

Date of registration: Oct 14th 2002

14

Wednesday, March 21st 2007, 12:37pm

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 :).

This post has been edited 1 times, last edit by "Currywurst mit Pommes" (Mar 21st 2007, 12:39pm)

  • Send private message

neon

Praktikant

  • "neon" is male

Posts: 11

Date of registration: Mar 15th 2007

15

Wednesday, March 21st 2007, 1:35pm

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?

This post has been edited 1 times, last edit by "neon" (Mar 21st 2007, 1:47pm)

  • Send private message

Scooby22

Trainee

  • "Scooby22" is male

Posts: 77

Date of registration: Sep 12th 2004

Location: Laatzen

Occupation: Angew. Informatik

16

Wednesday, March 21st 2007, 2:15pm

5 3 sin * cos 8 15 2 + * +

0 0 1 2 1 0 0 0 2 2 2

Bin mir eigentlich ziemlich sicher .

This post has been edited 2 times, last edit by "Scooby22" (Mar 21st 2007, 2:20pm)

  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

Posts: 438

Date of registration: Oct 14th 2002

17

Wednesday, March 21st 2007, 2:42pm

Quoted

Wie würdet ihr zu 3 c) antworten?


So wie es im Skript (main.pdf) steht :)
  • Send private message