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.
  • 1
  • 2

DrChaotica

Senior Schreiberling

  • "DrChaotica" is male
  • "DrChaotica" started this thread

Posts: 714

Date of registration: Jan 22nd 2005

Location: SHG

Occupation: SW-Entwickler

1

Friday, October 28th 2005, 8:53pm

Datenstrukturen und Algorithmen, Übung 3, Aufgabe 2 f+g

Hallo.

Der Rest war je relativ human, aber bei diesen Aufgaben stehe ich etwas auf dem Schlauch. Was mache ich bei 2g mit d(n)-e(n), wenn e(n) schneller wächst als d(n)? Macht O(..) von einer negativen Funktion Sinn, warum?

Für was steht jetzt genau das O im O(..)? Obere Schranke, Ordnung,...?

Mir fällt kein vernünftiger Ansatz für 2f ein, hat eventuell der Hinweis auf die Stirling-Formel genau mit dieser Teilaufgabe etwas zu tun? (Wenn nicht mit der, mit welcher dann?)

Für Rat und Tat, danke schonmal im Voraus :)
  • Send private message

Ray-D

Alter Hase

  • "Ray-D" is male

Posts: 690

Date of registration: Oct 9th 2002

Location: Zimbabwe-Island Ost Beiträge: 3.427

Occupation: Informatiker

2

Friday, October 28th 2005, 10:36pm

RE: Datenstrukturen und Algorithmen, Übung 3, Aufgabe 2 f+g

Quoted

Original von DrChaotica
Hallo.

Hallo :)

Quoted

Original von DrChaotica
Für was steht jetzt genau das O im O(..)? Obere Schranke, Ordnung,...?


Quoted

Wikipedia
Der Großbuchstaben "O" (damals eigentlich ein großes Omikron) als Symbol für "Ordnung von" wurde...
"ob ich alles weiss, was wir wissen, weiss ich auch nicht, aber ich weiss natürlich niemand von uns weiss etwas was er nicht weiss" - Wolgang Schäuble
Freiheit wird nicht erbettelt, sondern erkämpft

Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von »Ray-D« (Heute, 04:29)
  • Send private message

Teklan

Erfahrener Schreiberling

Posts: 267

Date of registration: Nov 13th 2004

Location: Hannover

3

Tuesday, November 1st 2005, 11:13pm

Ein paar Fragen zur Laufzeit:

Bedeuten z.B. 3 verschachtelte for-Schleifen gleich immer O(n^3), 5 verschachtelte for-Schleifen O(n^5) etc?

Aufg 1:

"Bestimmen Sie [...] O(...) bzgl der Laufzeit in Abhängigkeit von n und m" - Kann man z.B: O(n^2,1) schreiben wobei O(n^2,1) = g(n,m)???

Aufg 3 b)
"[..] und geben Sie dir Laufzeitkomplexität in Abh. von n und v an!"
- auch z.B: irgendwas in der Art von g(n,v) = O(n^2, 1)?

Danke für die HIlfe
  • Send private message

Dude

Junior Schreiberling

Posts: 181

Date of registration: Oct 11th 2004

4

Wednesday, November 2nd 2005, 6:39am

Quoted

Original von Teklan
Bedeuten z.B. 3 verschachtelte for-Schleifen gleich immer O(n^3), 5 verschachtelte for-Schleifen O(n^5) etc?

Immer? Nein. Oftmals? Ja.
  • Send private message

migu

free rider

  • "migu" is male

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

5

Wednesday, November 2nd 2005, 7:40am

Quoted

Original von Teklan
Bedeuten z.B. 3 verschachtelte for-Schleifen gleich immer O(n^3), 5 verschachtelte for-Schleifen O(n^5) etc?
Nein, denn die inneren Schleifen hängen nicht unbedingt von der Laufvariablen der äußeren Schleifen ab. Und selbst wenn, müssen nicht alle Schritte durchlaufen werden. Es kann also auch eine schwächere Laufzeitklasse herauskommen, z.B. O(n*n*log(n)). Man muss aber natürlich genau hinsehen oder zählen.
tar: Anlegen eines leeren Archivs wird feige verweigert.
  • Send private message

cjk

Praktikant

Posts: 10

Date of registration: Oct 8th 2005

6

Wednesday, November 2nd 2005, 9:37am

Quoted

Es kann also auch eine schwächere Laufzeitklasse herauskommen, z.B. O(n*n*log(n))

Hm, wie kommt man denn auf sowas mit Logarithmus?
  • 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)

7

Wednesday, November 2nd 2005, 10:03am

Quoted

Original von cjk

Quoted

Es kann also auch eine schwächere Laufzeitklasse herauskommen, z.B. O(n*n*log(n))

Hm, wie kommt man denn auf sowas mit Logarithmus?
Beispiel:

Eingabe: Eine natürliche Zahl n in Binärdarstellung.
Algorithmus: Durchlaufe alle Bits von n und bilde deren Summe
Ausgabe: Die binäre Quersumme von n

Laufzeit: O(log n)
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

Teklan

Erfahrener Schreiberling

Posts: 267

Date of registration: Nov 13th 2004

Location: Hannover

8

Wednesday, November 2nd 2005, 10:10am

Könnte jemand bitte Tipps zu meinen Problemen mit der Fragestellung bei Aufg1 und Aufgb 3 geben?
  • 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)

9

Wednesday, November 2nd 2005, 10:14am

Quoted

Original von Teklan
"Bestimmen Sie [...] O(...) bzgl der Laufzeit in Abhängigkeit von n und m" - Kann man z.B: O(n^2,1) schreiben wobei O(n^2,1) = g(n,m)???
O(...) hat nur ein Argument, nicht zwei (n^2 und 1) wie bei Dir. Im Inneren des O-Ausdrucks steht die Anzahl der Schritte, die der Algorithmus in Abhängigkeit von den Eingabegrößen benötigt. Dort sollte also insbesondere auch m vorkommen, es sei denn die Laufzeit ist von m unabhängig.

Quoted

"[..] und geben Sie dir Laufzeitkomplexität in Abh. von n und v an!"
- auch z.B: irgendwas in der Art von g(n,v) = O(n^2, 1)?
Genau wie oben. Wenn g eine Funktion in Abhängigkeit von zwei Variablen ist, dann wäre O(g(n, v)) zulässig. Das g gilt es natürlich herauszufinden.
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

Dude

Junior Schreiberling

Posts: 181

Date of registration: Oct 11th 2004

10

Wednesday, November 2nd 2005, 7:01pm

Quoted

Original von Teklan
Könnte jemand bitte Tipps zu meinen Problemen mit der Fragestellung bei Aufg1 und Aufgb 3 geben?


Quoted

Original von Teklan
Aufg 3 b)
"[..] und geben Sie dir Laufzeitkomplexität in Abh. von n und v an!"


Laufzeitkomplexität nur in Abhängigkeit von n, v ist dafür vollkommen irrelevant. Man soll in Abhängigkeit von n und v angeben, was der Algorithmus berechnet.
  • Send private message

q_2

Junior Schreiberling

Posts: 134

Date of registration: Oct 25th 2004

11

Thursday, November 3rd 2005, 2:46am

Chaotica, gib dir ein d(n)=e(n)+e(n).
1001 PHP-Klickibunti-made-by-Script-kiddies-Foren sind nicht nur Qual sondern auch Rückschritt!
  • Send private message

q_2

Junior Schreiberling

Posts: 134

Date of registration: Oct 25th 2004

12

Thursday, November 3rd 2005, 2:56am

Hier nur eine Spekulation, wenn jemand genaueres weiß, her damit:

O(1) = 1 und O(1) = 0
O(0) existiert nicht, weil es "keine Funktion" bedeuten würde. (O(0) = nihil)
1001 PHP-Klickibunti-made-by-Script-kiddies-Foren sind nicht nur Qual sondern auch Rückschritt!
  • Send private message

q_2

Junior Schreiberling

Posts: 134

Date of registration: Oct 25th 2004

13

Thursday, November 3rd 2005, 3:40am

Soeben wurde ich darauf hingewiesen, dass in O() "andere" Rechenregeln gelten könnten. ?(

Wenn die Subtraktion als Addition mit einer Additiv-Inversen bedeuten könnte (ja, den Gedanken hattest du auch), dann gib dir ein d(n)=e(n). Lasse mich bitte in dem Fall wissen, wie der Algorithmus dazu lautet, damit ich reich werden kann.
1001 PHP-Klickibunti-made-by-Script-kiddies-Foren sind nicht nur Qual sondern auch Rückschritt!
  • Send private message

DrChaotica

Senior Schreiberling

  • "DrChaotica" is male
  • "DrChaotica" started this thread

Posts: 714

Date of registration: Jan 22nd 2005

Location: SHG

Occupation: SW-Entwickler

14

Thursday, November 3rd 2005, 9:56am

Das hat sich inzwischen zwar schon erledigt, aber trotzdem danke für die Hinweise :)
Wieso sollten O(0) - Funktionen nicht existieren?, das ist doch nur Code, der nie ausgeführt wird. Und der hat laut Monsieur LaMothe die beste Laufzeit ;) ...

PS: Boah, hast du das wirklich nachts um halb vier geschrieben 8o
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

15

Thursday, November 3rd 2005, 3:48pm

O(1) ist einfach nur die Schreibweise für alle Algorithmen mit konstanter Laufzeit.
Ein Algorithmus der immer nur 10 Schritte macht, egal bei welcher Eingabe läuft in O(1). Ein Algorithmus mit nur 1 Schritt auch usw.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

migu

free rider

  • "migu" is male

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

16

Thursday, November 3rd 2005, 8:31pm

Quoted

Original von DrChaotica
Wieso sollten O(0) - Funktionen nicht existieren?, das ist doch nur Code, der nie ausgeführt wird. Und der hat laut Monsieur LaMothe die beste Laufzeit ;) ...
Auch wenn das alles ja eigentlich Unsinn ist: wenn der Code nie ausgeführt wird, hat er doch auch konstante Laufzeit, er gehört also zur Klasse O(1). ;)
tar: Anlegen eines leeren Archivs wird feige verweigert.

This post has been edited 1 times, last edit by "migu" (Nov 3rd 2005, 8:31pm)

  • Send private message

Lucky

Erfahrener Schreiberling

  • "Lucky" is male

Posts: 449

Date of registration: Oct 17th 2003

Location: Dresden

Occupation: Um ein bißchen mehr Ahnung zu haben als andere

17

Thursday, November 3rd 2005, 9:17pm

Hey Joachim, für Deine 2 blauen Sterne muss erst noch eine Bezeichnung gefunden werden :D
no risk no fun, no brain no pain nor gain
  • Send private message

Ray-D

Alter Hase

  • "Ray-D" is male

Posts: 690

Date of registration: Oct 9th 2002

Location: Zimbabwe-Island Ost Beiträge: 3.427

Occupation: Informatiker

18

Thursday, November 3rd 2005, 9:47pm

eigentlich müsste er "Almighty lord " sein (siehe hier)
"ob ich alles weiss, was wir wissen, weiss ich auch nicht, aber ich weiss natürlich niemand von uns weiss etwas was er nicht weiss" - Wolgang Schäuble
Freiheit wird nicht erbettelt, sondern erkämpft

Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von »Ray-D« (Heute, 04:29)
  • 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)

19

Thursday, November 3rd 2005, 11:00pm

Quoted

Original von Ray-D
eigentlich müsste er "Almighty lord " sein (siehe hier)
... das fand ich dann aber doch etwas viel des guten und habe mich für einen dezenten Strich entschieden. :)
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

DrChaotica

Senior Schreiberling

  • "DrChaotica" is male
  • "DrChaotica" started this thread

Posts: 714

Date of registration: Jan 22nd 2005

Location: SHG

Occupation: SW-Entwickler

20

Thursday, November 3rd 2005, 11:02pm

Übung 4, Aufgabe 1 a)

a) Geben Sie alle binären Bäume an, deren Knoten beim
1. Preorder- und Inorder-,
2. Preorder- und Postorder-,
3. Inorder- und Postorderdurchlauf
in genau derselben Reihenfolge durchlaufen werden. Begründen Sie Ihre Antworten.

Seltsam: Ist das nicht in allen drei Fällen nur ein Baum, der lediglich aus einer Wurzel besteht?

Der nächstgrößere binäre Baum, also
-----1
---2--3

würde doch schon mit allen Durchlaufarten anders durchlaufen werden:
PreOrder: 1,2,3
InOrder: 2,1,3
PostOrder: 3,2,1

Habt ihr Aufgabensteller eventuell an so welche Bäume gedacht?
An den
------o
----o
--o
o

und den hier?
o
--o
-----o
--------o

Die sind aber leider nach Definition im Skript nicht binär.
Oder sollte die Aufgabenstellung nicht eher lauten:

Geben Sie alle binären Bäume an, deren interne Knoten beim...bla
statt
Geben Sie alle binären Bäume an, deren Knoten beim...usw.

Oder bin ich einfach schon viel zu müde und sehe nicht, wo mein Fehler ist? Naja, mal schauen...

This post has been edited 1 times, last edit by "DrChaotica" (Nov 3rd 2005, 11:04pm)

  • Send private message
  • 1
  • 2