View Full Version : [Frage] Übungsblatt 1
Hi,
hab leider ein bisschen ein Problem mit BSp 1 und 2.
Bei Bsp 1 habe ich angenommen, das n0, das kleinste mögliche n ist das der Definition entspricht.
Wenn ich zum BSp eine Obere Schranke ermitteln will, wie bei unsererm BSp auf ÜB 1 dann habe ich eine Ungleichung wo links ein Ausdruck steht und rechts c. Ist c nun die Schranke od. die konstante mit der die Schranke multipliziert wird um der Ungleichung zu entsprechen?
Ich würde für bsp1 n teilbar durch 3: n0= 6 und c = 4
für nicht teilbar durch 3 : n0=1 c=4.
BSp3:
a) A: Theta(sqrt(n) logn)
B: Theta(sqrt(n)+n)
b)
C: Zeile2: n, Zeile: 3n, Zeile4: k=k/2
D:Zeile1: sqrt(n) Zeile5: x-1
BSP5:
23 Vergleiche 15 Bewegungen
BSP7:
Skriptum Zeile 5 und 8 gleicheitszeichen umdrehen --> partition
BSP8:
Zeile 5 gleicheitszeichen umdrehen.
BSP9:
Hier hab ich mir Überlegt das hier eigentlich nur der "Erstelle heap" Algorithmus durchlaufen wird und in Versickere kein Vertausch durchgeführt wird sondern eine Fehlermeldung ausgegenen wird.
A--> kein MAx Heap
B -- max Heap
BSP10:
In versickere Zeile 7 kleiner Zeichen umdehen.
Eine Bemerkung: Ich habe ansich alle Algorithmen in JAva ausprobiert, sollten eigentlich alle stimmen, wenn jemandem etwas auffällt was ich übersehen od. Vergessen habe bite posten danke!
Wenn ich zum BSp eine Obere Schranke ermitteln will, wie bei unsererm BSp auf ÜB 1 dann habe ich eine Ungleichung wo links ein Ausdruck steht und rechts c. Ist c nun die Schranke od. die konstante mit der die Schranke multipliziert wird um der Ungleichung zu entsprechen?
Die Konstante die man angibt ist nicht die Schranke. c * n^2 ist eine asymptotisch obere Schranke von f(n) falls f(n) = O(n^2).
michaelllll
24-10-2007, 23:21
Hi,
9.B -- max Heap
Ist meiner Meinung kein Max Heap:
da:
_______6
___3________5
_3___-1___4___-2
1 -1 0 -2 -3
In der 3. Zeile, 2. Spalte steht "-1" und das hat als Kind "0" und "-2". Da "-1" < "0" -> kein Maximumheap
Hi,
BSp3:
B: Theta(sqrt(n)+n)
Also ich habe dafür THETA(2^sqrt(n) + sqrt(n)) =THETA(2^n) rausbekommen.
Warum?
Also: Die erste Schleife wird sqrt(n) ausgeführt (das hast du ja auch).
In dieser Schleife wird dann immer a=a*2 gerechnet. Also wenn n = 25 ist, wird die 1. Schleife 5 mal durchlaufen und dadurch ist a=32
(1. Durchlauf a=1*2
2. Durchlauf a = 2 *2
3. Durchlauf a = 4*2
4. Durchaluf a = 8*2
5. Durchlauf a = 16 *2)
-> a=32 = 2^5 = 2^sqrt(n)
Beide Schleifen noch addieren und darum komme ich auf THETA(2^sqrt(n) + sqrt(n)) =THETA(2^n)
Aja: bei 1. Hab ich rausbekommen, dass O(n^2) falsch ist.
Also bei n nicht teilbar durch 3 ist:
0 <= 2n^3 * sqrt(n) - 1/(n^2) <= c*n^2
wenn ich da jetzt durch n^2 rechne bekomme ich:
0 <= 2n * sqrt(n) -1/(n^4) <= c
Nachdem die Konstante meines wissens nach nicht größer als n sein darf (weil ja n gegen unendlich strebt), kann da ja nicht stimmen, oder?
Beide Schleifen noch addieren und darum komme ich auf THETA(2^sqrt(n) + sqrt(n)) =THETA(2^n)
Warum ist die andere schleife sqrt(n) ?
michaelllll
25-10-2007, 13:15
Warum ist die andere schleife sqrt(n) ?
Die 1. Schleife ist sqrt(n), da i immer nur um 1 erhöht wird. Die Abbruchbedinung ist nun sqrt(n). Also wenn n = 25 wird die Schleife solange i < 5 = i < sqrt(25) durchgeführt.
Beispiellaufzeit:
Anfang: i = 1
1. Durchlauf:
i wird um 1 erhöht
i = 2 <= sqrt(25)
2. Durchlauf:
i wird um 1 erhöht
i = 3 <= sqrt(25)
3. Durchlauf:
i wird um 1 erhöht
i = 4 <= sqrt(25)
4. Durchlauf:
i wird um 1 erhöht
i = 5 <= sqrt(25)
5. Durchlauf:
i wird um 1 erhöht
i = 6 <= sqrt(25) FEHLER!! Bricht Schleife ab!!
Aja: bei 1. Hab ich rausbekommen, dass O(n^2) falsch ist.
Also bei n nicht teilbar durch 3 ist:
0 <= 2n^3 * sqrt(n) - 1/(n^2) <= c*n^2
wenn ich da jetzt durch n^2 rechne bekomme ich:
0 <= 2n * sqrt(n) -1/(n^4) <= c
Nachdem die Konstante meines wissens nach nicht größer als n sein darf (weil ja n gegen unendlich strebt), kann da ja nicht stimmen, oder?
Wieso soll die Konstante nicht größer als n sein dürfen steht ja nix in der Definition bzw gerade dadurch das n gegen unendlich strebt wirds sowieso irgendwann größer als c sonst wär c ja keine Konstante.
Bzw ich hab im Zweig nicht durch 3 teilbar:
0 \le 2n^3 \cdot \sqrt{n} - \frac{1}{n^2} \le c \cdot n^2 |:n^2
0 \le 2n \cdot \frac{\sqrt{n}}{n^2} - \frac{1}{n^4} \le c
Und wegen \lim_{n \to \infty} 2n = \infty ; \lim_{n \to \infty} \frac{\sqrt{n}}{n^2} = 0 ; \lim_{n \to \infty} \frac{1}{n^4} = 0
folgt
0 \le \infty \cdot 0 - 0 \le c
also wenn wie vorgeschlagen n_0 = 1 , c = 4 ist müsst das ja passen wenn ich richtig gedacht hab :)
Wieso soll die Konstante nicht größer als n sein dürfen steht ja nix in der Definition bzw gerade dadurch das n gegen unendlich strebt wirds sowieso irgendwann größer als c sonst wär c ja keine Konstante.
Bzw ich hab im Zweig nicht durch 3 teilbar:
0 \le 2n^3 \cdot \sqrt{n} - \frac{1}{n^2} \le c \cdot n^2 |:n^2
0 \le 2n \cdot \frac{\sqrt{n}}{n^2} - \frac{1}{n^4} \le c
Und wegen \lim_{n \to \infty} 2n = \infty ; \lim_{n \to \infty} \frac{\sqrt{n}}{n^2} = 0 ; \lim_{n \to \infty} \frac{1}{n^4} = 0
folgt
0 \le \infty \cdot 0 - 0 \le c
also wenn wie vorgeschlagen n_0 = 1 , c = 4 ist müsst das ja passen wenn ich richtig gedacht hab :)
I) Man darf mit uneigentlichen Grenzwerten nicht so rechnen.
II) 2n^3 \cdot \sqrt{n} - \frac{1}{n^2}\ :\ n^2\ =\ 2n \cdot \sqrt{n} - \frac{1}{n^4}\ \neq\ 2n \cdot \frac{\sqrt{n}}{n^2} - \frac{1}{n^4}
Aus II sieht man, dass die höchste Ordnung n \cdot \sqrt{n} ist, und für n → ∞ größer ist als jedes c. Somit wächst f(n) schneller als n^2 für beliebige Eingaben.
I) Man darf mit uneigentlichen Grenzwerten nicht so rechnen.
II) 2n^3 \cdot \sqrt{n} - \frac{1}{n^2}\ :\ n^2\ =\ 2n \cdot \sqrt{n} - \frac{1}{n^4}\ \neq\ 2n \cdot \frac{\sqrt{n}}{n^2} - \frac{1}{n^4}
Aus II sieht man, dass die höchste Ordnung n \cdot \sqrt{n} ist, und für n → ∞ größer ist als jedes c. Somit wächst f(n) schneller als n^2 für beliebige Eingaben.
Hehe hast natürlich recht ^^ Man sollt halt nichts Mathe mässiges machen wenn man am Vortag bisserl lang fort war :D
Naja anyway hier noch was zum Übungsblatt Aufgabe 6: http://www.informatik-forum.at/showpost.php?p=419695&postcount=6 <- im geposteten PDF Punkt 1.7
BSP5:
23 Vergleiche 15 Bewegungen
Hallo!
Wie kommst du da auf deine 23 Vergleiche und 15 Bewegungen?
Bei mir sind das 22 Bewegungen und 42 Vergleiche! (siehe Anhang)
Wo liege ich da falsch, oder stimmt das?
Ist meiner Meinung kein Max Heap:
da:
_______6
___3________5
_3___-1___4___-2
1 -1 0 -2 -3
In der 3. Zeile, 2. Spalte steht "-1" und das hat als Kind "0" und "-2". Da "-1" < "0" -> kein Maximumheap
Bin ich deiner Meinung --> beides kein max. Heap
LG Jacko
Also zuerst wegen dem Max Heap --> ist natürlich vollkommen korrekt, sind beide kein Maxheap. Hab mich da zu später stunde irgenwie vertan.
Wegen den Bewegungen und Vergleichen bei BSP 5:
Hier muß ich mich korrigieren Es sollten eigentlich gleich viele Bewegungen wie Vergleiche sein wenn man wie folgt überlegt:
solange i>0 und A[i]>key
hier bin ich eigentlich von der annahme ausgegangen das bei erfüllung der Bedingung ein Vergleich gerechnet wird. Jacko hat in seinem vorigen post aufgespalten in die Vergleich i>0 und A[i]>key --> wäre eigentlich richtiger.
Wenn man von meiner annahme ausgeht hätte man immer einen Vergleich
solange i>0 und A[i]>key
entweder die Schleife wird ausgeführt -->A[i+1]=a[i]; eine Bewegung,
oder schleife beendet --> a[i+1]=key;
i jedem Fall eine Bewegung.
Hallo!
Wie kommst du da auf deine 23 Vergleiche und 15 Bewegungen?
Bei mir sind das 22 Bewegungen und 42 Vergleiche! (siehe Anhang)
Wo liege ich da falsch, oder stimmt das?
lol ich hab 15 Bewegungen (eventuell 29 wenn das rausnehmen und reingeben des elements mitgerechnet wird) und 20 vergleiche (23 vergleiche könnt auch stimmen wenn man nochmal ganz links vergleicht ob i schon null ist) :D
Hallo!
Wie kommst du da auf deine 23 Vergleiche und 15 Bewegungen?
Bei mir sind das 22 Bewegungen und 42 Vergleiche! (siehe Anhang)
Wo liege ich da falsch, oder stimmt das?
Ich bin mir ziemlich sicher, dass du die Vergleiche mit i>0 nicht zu zählen brauchst da nur die Vergleiche zwischen 2 Zahlen gemeint sind ... dann würdest du auf
20 Vergleiche und 22 Bewegungen kommen
- und das waer auch gleichzeitig meine Loesung ;)
michaelllll
30-10-2007, 01:08
Ich bin mir ziemlich sicher, dass du die Vergleiche mit i>0 nicht zu zählen brauchst da nur die Vergleiche zwischen 2 Zahlen gemeint sind ... dann würdest du auf
20 Vergleiche und 22 Bewegungen kommen
- und das waer auch gleichzeitig meine Loesung ;)
Ich glaube auch, dass nur die Schlüsselvergleiche gemeint sind. Aber stimmt, eigentlich steht da nur Vergleiche...
IRBaboon
30-10-2007, 10:55
Ich glaube auch, dass nur die Schlüsselvergleiche gemeint sind. Aber stimmt, eigentlich steht da nur Vergleiche...
Yep, ist ungenau formuliert: Sollte wirklich Schlüsselvergleiche heissen.
I.R.Baboon
THETA(2^sqrt(n) + sqrt(n)) =THETA(2^n)
Hi, ich krieg das Selbe raus bis auf die Kleinigkeit, dass 2√n + √n = ϴ(2√n) ≠ ϴ(2n).
michaelllll
31-10-2007, 21:50
Hi, ich krieg das Selbe raus bis auf die Kleinigkeit, dass 2√n + √n = ϴ(2√n) ≠ ϴ(2n).
tja, da hast wohl recht!
DANKE!!!
michaelllll
31-10-2007, 21:51
Hat eigentlich schon jemand 6b gelöst?
Hi, zu Beispiel 5: ich krieg 20 Bew. bzw. 20 Vgl. raus, und zwar durch Abzählen der Pfeile bzw. durch Abzählen der notwendigen Vergleiche der "aktuellen" Zahl mit den bereits sortierten Zahlen links davon. Die aktuelle Zahl ist jeweils unterstrichen.
Bew | Vgl
44 55 1 | 1
--> -->
44 55 12 3 | 2
<------
--> -->
12 44 55 42 3 | 3
<------
12 42 44 55 94 1 | 1
--> --> --> -->
12 42 44 55 94 18 5 | 5
<--------------
--> --> --> --> --> -->
12 18 42 44 55 94 06 7 | 6
<----------------------
-->
06 12 18 42 44 55 94 67 2 | 2
<--
-------------------------------------------
Summe 22 | 20
EDIT: Auch wenn die aktuelle Zahl nicht getauscht werden muss, findet trotzdem eine Datensatzbewegung statt, vgl. Posting #21.
ich bekomme 20 Vergleiche und 15 Bewegungen raus.
@tonico : der untere pfeil sollte meiner meinung keine bewegung darstellen sonder eher zeigen wohin die zahl kommt. Die oberen pfeile stellen die bewegungen da. Du tauschst ja die zahlen solange bis die zahl im kreis an der richtigen stelle steht.
Die Vergleich Anzahl hab ich genau wie tonico. Bei der 94 muss man ja nur mit 55 vergleichen weil wir davon ausgehen sollen das alle zahlen links von der 55 schon kleiner als die 55 sind.
Wenn ich etwas falsches gesagt habe dann bitte belehrt mich :P
Für schon sortiert: 21 Vergleiche / 0 Bewegungen
umgekehrt soritert: 21 Vergleiche / 21 Bewegungen
Die Vergleich Anzahl hab ich genau wie tonico. Bei der 94 muss man ja nur mit 55 vergleichen weil wir davon ausgehen sollen das alle zahlen links von der 55 schon kleiner als die 55 sind.
Ja, hab ich auch so.
Für schon sortiert: 21 Vergleiche / 0 Bewegungen
Warum dann hier 21 Vergleiche? Ist doch wieder das gleiche wie oben. Es wird immer ausgegangen, dass das was links steht kleiner ist. Deshalb hab ich da nur 7 vergleiche. Also ich mein, sobald ich einmal nach links hüpfe und ich was kleineres hab bricht er ja ab. und das ist bei einer geordneten reihe ja der fall.
ich bekomme 20 Vergleiche und 15 Bewegungen raus.
@tonico : der untere pfeil sollte meiner meinung keine bewegung darstellen sonder eher zeigen wohin die zahl kommt. Die oberen pfeile stellen die bewegungen da. Du tauschst ja die zahlen solange bis die zahl im kreis an der richtigen stelle steht.
Wenn ich mir Insertion-Sort ansehe
01 für j = 2, ..., n {
02 key = A[j];
03 i = j - 1;
04 solange i > 0 und A[i] > key {
05 A[i + 1] = A[i];
07 i = i - 1;
08 }
09 A[i + 1] = key;
10 }
dann zähle ich "key = A[j]" in Zeile 2 und "A[i + 1] = key" in Zeile 9 genauso als eine Datensatzbewegung wie "A[i + 1] = A[i]" in Zeile 5.
EDIT: Ha! Da Zeile 2 und 9 immer ausgeführt wird sind es eigentlich 2 Bewegungen mehr, also 22.
EDIT 2: In der Zeilennummerierung oben ist ein Fehler, sollte aber egal sein.
naja, key = A[j] führt ja keine veränderung in der zahle folge hervor, es wird sich ja nur gemerkt wo der algorithmus als nächstes anfängt. Es ist keine bewegung im sinner der sortierung sondern eine Speicher bewegung.
Mal schauen was andere so sagen.
Ja, hab ich auch so.
Warum dann hier 21 Vergleiche? Ist doch wieder das gleiche wie oben. Es wird immer ausgegangen, dass das was links steht kleiner ist. Deshalb hab ich da nur 7 vergleiche. Also ich mein, sobald ich einmal nach links hüpfe und ich was kleineres hab bricht er ja ab. und das ist bei einer geordneten reihe ja der fall.
Ich hab mir das so überlegt:
Fall 1, sortiert:
Vergleiche: Die äußere Schleife läuft (n - 1)-Mal durch, beim 1. Durchlauf muss man die zweite Zahl mit der ersten vergleichen, beim 2. Durchlauf die dritte mit der zweiten usw., also bei jedem Durchlauf ein Vergleich, also n - 1 = 7 Vergleiche.
Bewegungen: Es wird jedes Mal eine Bewegung durchgeführt obwohl Datensätze nicht getauscht werden (vgl. Pseudocode in Posting #21), also wieder n - 1 = 7.
Fall 2, umgekehrt sortiert:
Vergleiche: In jedem Durchlauf der äußeren Schleife wird immer die aktuelle Zahl mit allen Zahlen links davon verglichen, also
1 + 2 + ... + n - 1 = n (n - 1) / 2 = 28
Bewegungen: In jedem Durchlauf der äußeren Schleife wird die aktuelle Zahl an den Anfang bewegt und alle Zahlen davor um eins nach rechts bewegt, also
2 + 3 + ... + n = n (n + 1) / 2 - 1 = 35
naja, key = A[j] führt ja keine veränderung in der zahle folge hervor, es wird sich ja nur gemerkt wo der algorithmus als nächstes anfängt. Es ist keine bewegung im sinner der sortierung sondern eine Speicher bewegung.
Mal schauen was andere so sagen.
So hab ich das nicht gemeint, A[j] = key und A[i + 1] = key entspricht einer Datensatzbewegung.
Ja, dann hast das eh auch so. hab auch 7 bzw. 28 vergleiche rauskriegt. :bounce:
Die vergleiche bei der sortierten Folge sind 7 wie ihr gesagt habt, aber bei den bewegungen bin ich mir nicht sicher, denn was bewegst du grafisch in einer bereits sortierten reihenfolge? Wenn du dir zeile 1 anschaust, startet j bei 2, zeile 4 zeigt das i bei j-1 anfängt, also 1,
A[i+1] ist daselbe feld wie A[j]. daher denke ich nicht dass das eine bewegung ist. Also bei der sortierten reihenfolge, da die while schleife nie ausgeführt wird.
Vergleiche 7 / Bewegungen 0
Umgekehrte Reihenfolge:
Habt ihr recht, hab ne zahl ausgelassen haha und daswegen auf 21 gekommen. Also 28 Vergleiche stimmt und es sind dann 35 Bewegungen, da wir dieses mal das größere element in [i+1] speicher, also j, danach i um eins runtersetzen und dann den key in [i+1] speichern.
Der erste Teil der Aufgabe ist dann auch 20 Vergleiche / 20 Bewegungen. Danke für die korrektur :P aber wie gesagt, bei einer bereits sortierten reihenfolge denke ich immer noch das es 0 Bewegungen sind.
Danke für die korrektur :P aber wie gesagt, bei einer bereits sortierten reihenfolge denke ich immer noch das es 0 Bewegungen sind.
hmm in skriptum S. 26 steht "Datenbewegungen gibt es in den Zeilen 2,6 und 9 von Algorithmus 1" dann nach vor blättern zu S. 14. lt. angabe sollen wir ja die vergleiche und bewegungen zählen. hab auch 7 vergl. und 0 bewegungen aber jetzt bin ich auch am überlegen mit den bewegungen...
A[i+1] ist daselbe feld wie A[j]. daher denke ich nicht dass das eine bewegung ist.
Also die Frage ist ob A[j] = A[j] auch eine Datenbewegung ist. Ich würde sagen ja. Andererseits steht im Skriptum (SS07 S. 28) bei Selection-Sort, dass A[j] = A[j] als Datenbewegung gezählt wird.
Der erste Teil der Aufgabe ist dann auch 20 Vergleiche / 20 Bewegungen. Danke für die korrektur :P aber wie gesagt, bei einer bereits sortierten reihenfolge denke ich immer noch das es 0 Bewegungen sind.
Naja, eigentlich 22/20 weil ja A[j] = A[j] auch zählt.
kann es sein das ihr das zu kompliziert angeht?
im skriptum auf Seite 17 steht das Insertion Sort seinen Best Case hat, wenn die Reihe bereits sortiert ist und den worst case, wenn die reihe umgekehrt sortiert ist!
wenn ich mir jetzt die seite 21 im skriptum anschaue und Cbest bzw. Cworst mit theta(n) und theta(n²) bzw. Mbest und Mworst mit theta(n) und theta(n²)
dann wars das doch! einfach einsetzen und ich hab mein ergebnis!
Cbest = Mbest = theta(8)
bzw.
Cworst = Mworst = theta(64)
oder denke ich da wiederum zu einfach?
ich komme mittlerweile auch auf 22 Bewegungen und 20 Vergleiche
lg jacko
dann werd ich mich euch wohl anschliessen und die 2 A[j] = A[j] mit zählen.
Also 20 Vergleiche und 22 Bewegungen.
Jacko es geht ja um genau diese EINE liste die wir haben, daher kommen die ganzen zahlen.Aber sonst hast du recht das man den best und worst case benutzen kann.
kann es sein das ihr das zu kompliziert angeht?
Glaub nicht, bis jetzt hab ich einfach nur Bewegungen bzw. Vergleiche abgezählt, vgl. Posting #18.
im skriptum auf Seite 17 steht das Insertion Sort seinen Best Case hat, wenn die Reihe bereits sortiert ist und den worst case, wenn die reihe umgekehrt sortiert ist!
wenn ich mir jetzt die seite 21 im skriptum anschaue und Cbest bzw. Cworst mit theta(n) und theta(n²) bzw. Mbest und Mworst mit theta(n) und theta(n²)
dann wars das doch!
Ja, nur dass die genaue Anzahl von Bewegungen bzw. Vergleichen gefragt ist, nicht die Abschätzung der Laufzeit.
Glaub nicht, bis jetzt hab ich einfach nur Bewegungen bzw. Vergleiche abgezählt, vgl. Posting #18.
Ja, nur dass die genaue Anzahl von Bewegungen bzw. Vergleichen gefragt ist, nicht die Abschätzung der Laufzeit.
Aber wie willst du das berechnen? Mit abzählen funktionierts - aber das wird nicht der sinn der sache sein denk ich mal!
Aber wie willst du das berechnen? Mit abzählen funktionierts - aber das wird nicht der sinn der sache sein denk ich mal!
Berechnen kann man es wie in Posting #23, man kann durch Abzählen auf die Formel kommen.
dann wird das wohl so passen! bin mal gespannt was die leute in der übung sagen!
edit: hab den eigenen thread zu bsp. 1 übersehen
lg jacko
frage...
wie komm ich bei bsp 3/b/C auf die lösung: n, 3*n, k/2?
gibts da ein kochrezept, wie ich so ein bsp lösen kann?
danke im voraus...
log n kommt immer dann vor wenn man eine division durch eine zahl hat und dann gerundet wird.
das n kommt dann davon das die schleife n mal durchläuft, also tust du ein n bei dem für hin, damit du aber den log n rausbekommst muss k diese division haben und daher muss k den wert von n anehmen, 3*n oder n oder 2*n etc, hauptsache n steht dort. Damit ist k ein vielfaches von n und wird in logeritmischer zeit abgebaut (k/2).
So habe ich es jedenfalls gelöst.
Hoffe das hat geholfen.
Wenn ich mir Insertion-Sort ansehe
01 für j = 2, ..., n {
02 key = A[j];
03 i = j - 1;
04 solange i > 0 und A[i] > key {
05 A[i + 1] = A[i];
07 i = i - 1;
08 }
09 A[i + 1] = key;
10 }dann zähle ich "key = A[j]" in Zeile 2 und "A[i + 1] = key" in Zeile 9 genauso als eine Datensatzbewegung wie "A[i + 1] = A[i]" in Zeile 5.
EDIT: Ha! Da Zeile 2 und 9 immer ausgeführt wird sind es eigentlich 2 Bewegungen mehr, also 22.
EDIT 2: In der Zeilennummerierung oben ist ein Fehler, sollte aber egal sein.
Ich sehe die Sache genauso, dass Zeile 2 und 9 (Bewegung) immer ausgeführt werden (siehe Skriptum) - sprich die Mindestanzahl an ausgeführten Bewegungen pro Sortiervorgang ist zwei. Wie ist es dann möglich, dass du für die erste Iteration nur eine Bewegung veranschlagst (imho in jedem Sortiervorgang eine zu wenig). Möglich dass ich grad ein wenig auf der Leitung steh, aber wollt nochmal rückfragen, bevor die Lösung als 100%ig durchgeht.
Lg, Jan
Ich habe problem mit Bsp 3A:( kann bitte jemand das Bsp hier erklären so ungefähr wie 3B erklärt wurde, das habe ich verstanden, aber woher kommt logn in 3A?
Danke
also, die antwort ist (wurzel)n*logn (die for schleife wird (wurzel)n mal durchgeführt weil j=(wurzel)n ist). Wie oben erwähnt bedeutet eine division durch irgendwas immer log weil n logarithmisch verkleinert wird, und dann wird immer die innere schleife ausgeführt.
man kann die basis von logs weglassen weil sie eher ein koeffizient sind und die werden bei laufzeit nicht berücksichtig (in 3A wäre es log zur basis 2 da a durch 2 dividiert wird).
Hoffe das hat etwas geholfen.
Ich sehe die Sache genauso, dass Zeile 2 und 9 (Bewegung) immer ausgeführt werden (siehe Skriptum) - sprich die Mindestanzahl an ausgeführten Bewegungen pro Sortiervorgang ist zwei. Wie ist es dann möglich, dass du für die erste Iteration nur eine Bewegung veranschlagst (imho in jedem Sortiervorgang eine zu wenig). Möglich dass ich grad ein wenig auf der Leitung steh, aber wollt nochmal rückfragen, bevor die Lösung als 100%ig durchgeht.
Lg, Jan
Ich rechne
key = A[j];
A[i + 1] = key;
als eine Datensatzbewegung, weil ich nur einmal das Array verändere, eine bessere Erklärung habe ich nicht, und im Skriptum ist auch keine. Wenn ich
A[i + 1] = A[j]
betrachte, ja dann kann das nur effizienter sein als das obige wenn der Output von A[j] nach A[i + i] gestreamt wird wenn man sich das so vorstellen darf :). Ich nehm aber an, dass der Computer in der Regel zuerst A[j] in den Speicher liest und dann diesen Wert nach A[i + 1] schreibt.
ich stimme tonico zu, ich denke auch das key nur eine hilfsvariable ist und nichts mit unserem Array, die Liste, zu tun hat, daher ist es nur eine bewegung.
andere schreibweise für key = A[j]; A[i+1] = key ist
A[i+1] = key = A[j];
da kann man sehen das es nur eine Bewegung im zusammenhang mit dem Array gibt, unsere Liste. Vieleicht hilft das weiter.
Ich rechne
key = A[j];
A[i + 1] = key;
als eine Datensatzbewegung, weil ich nur einmal das Array verändere, eine bessere Erklärung habe ich nicht, und im Skriptum ist auch keine. Wenn ich
A[i + 1] = A[j]
betrachte, ja dann kann das nur effizienter sein als das obige wenn der Output von A[j] nach A[i + i] gestreamt wird wenn man sich das so vorstellen darf :). Ich nehm aber an, dass der Computer in der Regel zuerst A[j] in den Speicher liest und dann diesen Wert nach A[i + 1] schreibt.
Ich geb euch aus programmiertechnischer Sicht natürlich Recht. Das Skriptum (SS 06 - also etwas älter) sagt mir jedoch in Kapitel "Sortieren durch Einfügen" --> "Datenbewegungen gibt es in den Zeilen 2,6 und 9". Wollt ich nur angemerkt haben, natürlich ist deine Erklärung schlüssig.
Lg, Jan
Blutsturz
03-11-2007, 14:31
Für schon sortiert: 21 Vergleiche / 0 Bewegungen
umgekehrt soritert: 21 Vergleiche / 21 Bewegungen
http://www.cs.hope.edu/alganim/animator/Animator.html
also wenn man sich hier dieses Tool mal zu Gemüte führen will, da wird einem gezeigt, dass es bei n=8 so aussieht:
bereits aufsteigend sortiert: 7 Vergleiche/ 7 Bewegungen
absteigend sortiert: 35 Vergleiche/ 7 Bewegungen
da muss man sich aber fragen warum der beste fall die gleiche anzahl an bewegungen hat wieder der schlechteste, da stimmt was nicht.
Das Zitat ist auch aus einem älteren post, ich habe meine Antwort schon geändert.
bereits sortiert: 7/7
umgekehrt sortiert: 28/35
Dieser code sollte das problem lösen: Ich bekomm C=22, M=15
public class InsertionSort {
/**
* @param args
*/
public static void main(String[] args) {
int A[] = { 44,55,12,42,94,18,6,67 }; // unsortiert
//int A[] = { 6,12,18,42,44,55,67,94 }; // sortiert
//int A[] = { 94,67,55,44,42,18,12,6 }; // umgekehrt sortiert
int key;
int i;
int vergleiche = 1;
int datenbewegungen = 0;
for (int j = 2; j < A.length; j++) {
key = A[j];
i = j - 1;
vergleiche++;
while (i >= 0 && A[i] > key) {
datenbewegungen++;
vergleiche++;
A[i + 1] = A[i];
i = i - 1;
}
A[i + 1] = key;
}
for (int x = 0; x < A.length; x++) {
System.out.print(A[x] + ", ");
}
System.out.println("\nVergleiche: " + vergleiche);
System.out.println("Datenbewegungen: " + datenbewegungen);
}
}
hi
obwohl ich glaube das über aufgabe 5 schon genung gesagt wurde. will ich anmerken das in der aufgabe kein direkter algo angegeben wurde nur allgemein von insertion-sort. weil man könnt ja z.b.
A[i+1] = key ersetzen durch if (j ungleich i +1) dann A[i+1] = key
dann fällt ja diese angeblich obligatorische bewegung weg. also ich zähle nur die "echten" bewegungen.
gerade listen hab ich v= n-1 und b=0
umgekehrt hab ich v=(n*(n+1))/2 - 2 b=(n*(n-1))/2 -1 //edit fehler
lg spjoe
Ich hab das ganze auch vesucht mit Java zu lösen:
/*
Schlüsselvergleiche: while...
Datenbewegungen:
- key = A[j];
- A[i+1] = A[i];
- A[i+1] = key;
*/
public class bsp_5 {
public static void main (String args[]) {
int [] Q = {44,55,12,42,94,18,6,67};
int [] R = {6,12,18,42,44,55,67,94};
int [] S = {94,67,55,44,42,18,12,6};
int key, i;
int b=0, v=0;
int [] A = S;
for (int j=1; j<A.length; j++)
{
key = A[j]; b++;
i = j-1;
if(i>=0 && (A[i] <= key)) v++;
while (i>=0 && A[i] >key)
{
A[i+1] = A[i]; b++;
i = i-1;
v++;
if(i>=0 && A[i] <= key) v++;
}
A[i+1] = key; b++;
}
for (i=0; i<A.length; i++)
System.out.print(A[i] + ", ");
System.out.println("\nSchlüsselvergleiche: " + v);
System.out.println("Bewegungen: " + b);
}
}
Vorallem mit den Vergleichen bin ich mir etwas unsicher, aber ich habe es mal aus progammiertechnischer Sicht versucht zu lösen.
quotenschwarze
05-11-2007, 09:29
also ich würd meinen, dass bei 3A THETA(n * sqrt(n)) rauskommt und nicht THETA(log n * sqrt(n)), weil a auf 2^n initialisiert wird und in jedem schleifendurchgang halbiert. Bei n=5 -> 2^5 = 32
1. 32/2 = 16
2. 16/2 = 8
3. 8/2 = 4
4. 4/2 = 2
5. 2/2 = 1
6. abbruch
-> 5 Schritte (=n) also THETA(n * sqrt(n))
Frage zu 5
wenn die zahlen umgekehrt sortiert sind hab ich ja nach jedem Vergleich auch gleich eine Datenbewegung also ich vergleich zb. am anfang 8,7,... -> 7 <8 also 1 vergleich und 1 datenbewegung weil ich ja 7 und 8 austausche...steht dann da 7,8,6,5,.... das geht dann soweit bis halt alles sortiert ist und dann hab ich gesamt 28 vergl. und 28 bewegungen
so, wo ist jetzt der wurm drin
konnte aus den vorigen threads nicht so wirklich schlau werden
das problem hab ich dann auch bei der "originalfolge" wie sie auf dem Angabeblatt steht...da komm ich auch 20/15 :(
danke
ich habe eine frage zu 9: in der Angabe steht Feld A, damit ist einfach
ein Array gemeint oder? Soll überprüft werden, ob das gesamte Array ein
MaxHeap ist oder ob Elemente des Arrays ein MaxHeap bilden? Wenn 1. der
Fall wäre, müsste man ja nur von links nach rechts durchgehen und immer
die 2 nächsten Werte mit dem Wert links vergleichen, dann wechselt man
zwei Werte nach links und vergleich die nächsten zwei mit diesem etc...
aufgabe 8 habe ich nicht so gemacht wie im skript, sondern ich habe
die liste immer wirklich in zwei teile aufgeteilt, da das ganze so durchsichtiger
ist. ist das ein problem?
finde so sieht man die Rekursion viel besser.
@ AliK: bei sortierung einer absteigend sortierten liste von n elementen
hast du für das i-te element i vergleiche und i+1 bewegungen, wenn ich
dsa richtig verstanden habe. zb bei element 1 hast du 1 vergleich und
2 bewegungen, element 0 auf 1 und 1 auf 0, beim 2. hast du 2 vergleiche
und 3 bewegungen etc. so komme ich auf 28 vergleiche und 35 bewegungen.
also ich würd meinen, dass bei 3A THETA(n * sqrt(n)) rauskommt und nicht THETA(log n * sqrt(n)), weil a auf 2^n initialisiert wird und in jedem schleifendurchgang halbiert. Bei n=5 -> 2^5 = 32
1. 32/2 = 16
2. 16/2 = 8
3. 8/2 = 4
4. 4/2 = 2
5. 2/2 = 1
6. abbruch
-> 5 Schritte (=n) also THETA(n * sqrt(n))
Das halbieren und abrunden ist laufzeitmäßig immer logn.Ist auch so bei jedem Beispiel das wir gemacht haben. Das n wird logarithmisch abgebaut, wie du oben zeigst. Daher es wird langsamer als sqrt(n) abgebaut: z.B. von 16 würdest du mit sqrt(n) gleich auf 4 kommen aber wir haben noch die 8 dazwischen also kann das nicht stimmen.
@Max Heap bedeutet dass das größte element an der Wurzel steht. Das heist du schaust dir den ganzen baum an und siehst nach ob das größte an der Wurzel ist. Dann schaust du dir die 2 Teilbäume an, also die Kinder von der Wurzel, und schaust wieder nach, das machst du rekursiv bis du nur noch elemente hast ohne kinder, also blätter.
Wegen bsp 8. der algorithmus selber halbiert die folge solange bis jedes element für sich eine Folge ist und dann werden immer 2 folgen zusammengefügt also passt dein Ansatz.
Wegen den Vergleichen und Bewegungen. Man hat immer eine Bewegung mehr weil man das element das als key benutzt wird auch bewegt werden muss (siehe zeile 2 UND 9); zusammen stellen sie die extra Bewegung da.
Hoffe das hat euch weiter geholfen.
quotenschwarze
06-11-2007, 11:41
Das halbieren und abrunden ist laufzeitmäßig immer logn.Ist auch so bei jedem Beispiel das wir gemacht haben. Das n wird logarithmisch abgebaut, wie du oben zeigst. Daher es wird langsamer als sqrt(n) abgebaut: z.B. von 16 würdest du mit sqrt(n) gleich auf 4 kommen aber wir haben noch die 8 dazwischen also kann das nicht stimmen.
ja, wenn a = n wäre, dann hätt ich auch gesagt, dass der aufwand logn ist. aber a wird auf 2^n initialisiert und deswegen beträgt der aufwand meiner meinung nach nur n.
BSP8:
Zeile 5 gleicheitszeichen umdrehen.
also irgendwie kann das nicht stimmen oder? meinst du damit nur den merge-sort oder auch den merge?
weil wenn du beim merge gleich das erste "<" umdrehst kommt man auf l > r und das kann doch nie stimmen...
Hier muss nur das <= auf >= inerhalb des Merge Algoritmus geändert werden.
boesebiene
06-11-2007, 23:04
ich habe eine frage zum ersten beispiel, draufgekommen auf den sachverhalt bin ich, weil ich die tabelle versucht habe zu lösen.
wenn ich in 3n^2-7n*(n)^(1/2)+pi zum beispiel 3 einsetze (also 3*9-21*(3)^(1/2)+pi), was ja erlaubt ist da 3 durch 3 teilbar ist, dann bekomme ich ein negatives endergebnis. aber wie kann ein algorithmus eine negative laufzeit aufweisen? irgendwie bin ich verwirrt. hab ich wo einen denkfehler? ...
Paulchen
06-11-2007, 23:21
wenn ich in 3n^2-7n*(n)^(1/2)+pi zum beispiel 3 einsetze (also 3*9-21*(3)^(1/2)+pi), was ja erlaubt ist da 3 durch 3 teilbar ist, dann bekomme ich ein negatives endergebnis. aber wie kann ein algorithmus eine negative laufzeit aufweisen? irgendwie bin ich verwirrt. hab ich wo einen denkfehler? ...Negative Laufzeit ist natürlich etwas realitätsfern. Es macht aber auch bei solchen Funktionen Sinn, sich das asymptotische Verhalten für große n zu überlegen (man muss dabei natürlich von der Vorstellung Abstand nehmen, es handle sich um Laufzeiten von Algorithmen, und mit den Funktionen an sich arbeiten). Der Landau-Notation sind solche Ausreißer nämlich egal. Wesentlich ist, dass die entsprechende(n) Bedingung(en) ab einem gewissen n0 für alle n gelten, was sich davor abspielt, ist ganz egal.
boesebiene
07-11-2007, 00:24
danke! :)
nachdem ja eh schon besprochen wurde, dass man im merge nur in der zeile 5 <= durch ein >= ersetzten muss, was ja auch logisch ist, da es der einzige vergleich ist.
ich habe jetzt mal herausgearbeitet was nach jedem rekursiven aufruf sich geändert hat, wenn mir das jmd bestätigen od mich auf fehler hinweise könnte wärs sehr hilfreich für mich :)
also mal aufteilen von
<9 0 5 8 2 6 3 8> in
9 0 5 8 2 6 3 8
9 0 5 8 2 6 3 8
9 0 5 8 2 6 3 8 // jetzt mal alles aufgeteilt
9 0 8 5 6 2 8 3 // 1. sortierung durchgeführt
9 8 5 0 8 6 3 2 // 2. sortierung
9 8 8 6 5 3 2 0 // 3. sortierung und gleichzeitig das ergebnis
passt das so?
jep richtig ^^ hättest es auch einfach aufschreiben können
jep richtig ^^ hättest es auch einfach aufschreiben können
thx :)
timurlan2
07-11-2007, 15:21
Hallo Leute!
Wie hat die Übungsstunde ausgeschaut?
Wie viele Beispiele wurden vorgerechnet?
Danke im vorhinaus. Könnte wer vielleicht die Ergebnisse posten?
Mfg Timur
timurlan2
07-11-2007, 15:38
Hallo,
könnte vieleicht jemand Bsp. 6 posten? Ich habe alles aufgezeichnet, aber mit der Erklärung tue ich mir schwer...
Bzw. wie wurde in der Übungsstunde danach gefragt?
Danke.
Lg
richtige Lösung steht bereits im Forum unter 1.6 würd da mal reinschaun, viel anders kannst es nicht machen :omg:
aufzeichnen vergleiche bewegungen dazuschreiben mit formel gegenprüfen fertig
rest steht im skriptum
Wie bestimmt man ob die Fachverteilung stabil, instabil ist; bezüglich der Aufgabe 7.
sorry, falsch gepostet, hatte zu viele tabs offen :D
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.