View Full Version : [FRAGE] - Beispiel 1.6
Hi,
Hat sich schon jemand mit Bsp. 1.6 befasst?
Meine Überlegungen:
Anzahl der Schlüsselbewegungen ist N (1 Bewegung pro Element - siehe auch Skriptum Seite 28).
Anzahl der Schlüsselvergleiche ist N*(N-1)/2 (ebenfalls Skriptum - Seite 29).
Wie ist das aber nun mit den beiden Beispielen gemeint? Ich meine es ist "schön", dass die Zahlenfolgen verschieden aussehen, aber die Schlüsselbewegungen sind sowieso immer N und auch die Schlüsselvergleiche bleiben auf N*(N-1)/2, egal an welcher Position im rechten, unsortierten Teil das Tauschelement ist - es werden ja immer alle verbleibenden Tauschelemente durchsucht.
Wo denk ich da falsch?
Danke und lg
Thomas
http://www.informatik-forum.at/showpost.php?p=461873&postcount=8
hi ihr wisst aber schon das das beispiel 7 ausm letzten semester nicht gleich ist wie das beispiel 6. letzte semester wurde das beispiel mit insertion sort und dieses jahr mit selection sort gefragt :)
das is natürlich ein argument ^^ aber gibt ja zumindest mal einen denkanstoß :D
stimmt aber die Lösung von #1 is schon so ziemlich richtig für Schlüsselvergleiche
N*(N-1) / 2
stimmt für egal welche Folge von Zahlen
und für die die Bewegungen tendiere ich zwischen
2N-2 bzw. 3(N-1)
je nachdem wie man die Umspeicherung in die jeweilige Hilfsvariable ansieht ;)
(also das Vertausche => entweder als 2 oder 3 )
15 <=> 3
A[i] = 15
A[j] = 3
A[h] = 0
A[h] = A[j] //1. Schlüsselbewegung
A[j] = A[i] //2. Schlüsselbewegung
A[i] = A[h] //3. Schlüsselbewegung
das wärs für 3(N-1)
und vereinfacht ohne hilfsvariable 2N-2
is denk ich irrelevant da in theta Notation sowieso im n rauskommt :verycool:
stimmt aber die Lösung von #1 is schon so ziemlich richtig für Schlüsselvergleiche
N*(N-1) / 2
stimmt für egal welche Folge von Zahlen
Würd ich auch sagen.
und für die die Bewegungen tendiere ich zwischen
2N-2 bzw. 3(N-1)
je nachdem wie man die Umspeicherung in die jeweilige Hilfsvariable ansieht ;)
(also das Vertausche => entweder als 2 oder 3 )
Ich krieg für die Anzahl der Vertauschungen N-1 (N gerade) bzw. N-2 (N ungerade). Für eine Vertauschung würde ich intuitiv 2 Datenbewegungen rechnen:
val = A[j];
A[j] = A[minpos]; // 1. Datensatzbewegung
A[minpos] = val; // 2. Datensatzbewegung
Aber wie Du schon gesagt hast ist das ja letztlich egal.
Zu den Datenbewegungen für b) hab ich mir gedacht, schlechter als der Worst-Case ϴ(n) kanns nicht werden, also bleibt nur noch zu überlegen obs besser (z.B. ϴ(log(n))) werden kann. Intuitiv würde ich sagen, es kann nicht besser werden, mir fehlt nur noch das Killerargument.
dein Killerargument was du brauchst is folgendes ;),
mit ausnahme eines Konstanten Faktor ändert sich gar nix an dem eigentlich n, weil es müssen immer Minmum n - 1 Schlüsselbewegungen sein, es wird das aktuell kleinste gesucht und dann umgespeichert (selbst wenn das Element richtig steht) und das is eine Schlüsselbewegung
:coolsmile:
dein Killerargument was du brauchst is folgendes ;),
mit ausnahme eines Konstanten Faktor ändert sich gar nix an dem eigentlich n, weil es müssen immer Minmum n - 1 Schlüsselbewegungen sein, es wird das aktuell kleinste gesucht und dann umgespeichert (selbst wenn das Element richtig steht) und das is eine Schlüsselbewegung
:coolsmile:
Bei dem PseudoCode in meinem Skriptum (SS07 S.28) ist eine Bedingung enthalten:
falls minpos > j dann {
Vertausche
}
Lässt man diese Bedingung weg stimme ich sofort zu. Mit dieser Bedingung könnte sich die Ordnung der Datenbewegungen vielleicht noch verbessern. Wählt man N=8 stehen 3 Elemente bereits richtig, bei N=32 sogar 7. Ich hab das für ein paar Werte ausprobiert und es scheint vernachlässigbar zu sein, nur ist das kein gutes Argument.
ja stimmt schon, bei dieser Zahlenfolge egal welches N sollt es immer auf ein theta n hinauslaufen ;)
michaelllll
03-11-2007, 16:50
Lässt man diese Bedingung weg stimme ich sofort zu. Mit dieser Bedingung könnte sich die Ordnung der Datenbewegungen vielleicht noch verbessern. Wählt man N=8 stehen 3 Elemente bereits richtig, bei N=32 sogar 7. Ich hab das für ein paar Werte ausprobiert und es scheint vernachlässigbar zu sein, nur ist das kein gutes Argument.
Naja, habs mir schon öfters angesehen und fehlt auch nichts besseres ein. Immerhin ist ja die Theta noation nicht so genau, sondern ja nur ungefähr. Wohl auch kein Killerargument...
Hmm.. aber bei Mavg=THETA(n) wenn ich mich richtig erinnere (hab das Skriptum in Wien vergessen). Vielleicht könnte man unser beispiel irgendwie so argumentieren, wie das wir das Mavg=THETA(n) argumentiert.
hab das jetzt nachprogrammiert und mal einige beispiele getestet:
Bsp. a)
Eingabefolge:
4, 5, 6, 7, 8, 1, 2, 3 | n=8; 28 Vergleiche - 7 Bewegungen
5, 6, 7, 8, 9, 1, 2, 3, 4 | n=9; 36 Vergleiche - 8 Bewegungen
10 ... 20, 1....9 | n=20; 190 Vergleiche - 19 Bewegungen
11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 | n=21; 210 Vergleiche - 20 Bewegungen
Bsp. b)
Eingabefolge:
4, 5, 3, 6, 2, 7, 1, 8 | n= 8; 28 Vergleiche - 4 Bewegungen
5, 6, 4, 7, 3, 8, 2, 9, 1 | n= 9; 36 Vergleiche - 8 Bewegungen
10, 11, 9, 12, 8, 13, 7, 14, 6, 15, 5, 16, 4, 17, 3, 18, 2, 19, 1, 20 | n= 20; 190 Vergleiche - 16 Bewegungen
11, 12, 10, 13, 9, 14, 8, 15, 7, 16, 6, 17, 5, 18, 4, 19, 3, 20, 2, 21, 1 | n=21; 210 Vergleiche - 18 Bewegungen
scheint wohl die formel mit n*(n-1) / 2 für die vergleiche zu stimmen!
die bewegungen verhalten sich etwas komisch!
vl hilfts ja wem!
EDIT:
Kann mir jemand erklären was das beispiel für einen sinn hat?
wenn ich jetzt sag meine formel für die vergleiche ist n*(n-1) / 2
dann komm ich doch sowieso auf ein theta(n²)
und bei den bewegungen auf ein theta(n)
genau wie es im skriptum auf seite 28 steht!
kann mir auch noch jemand sagen wie man ohne die zeile 9 auf 3*(n-1) kommt? kann mir nicht erklären wo der 3er herkommt!
lg jacko
Hi Jacko,
Du sprichst in deinem EDIT genau meinen Ansatz aus Post #1 an.
Die Schlüsselvergleiche sind immer theta(n^2) (weil C-Worst = C-Avg = C-Best) und die Bewegungen sind immer theta(n) (weil auch hier M-Worst = M-Avg = M-Best gilt).
Ich versteh auch nicht ganz was der Sinn des Beispiels ist, denn die Inputreihenfolge beim Selection-Sort hat keine Auswirkungen auf die Laufzeiten - vielleicht wollen sie genau das hören???
@ 3*(n-1):
Das kommt daher, dass ja die Funktion "Vertauschen" 3 Datenbewegungen macht:
hilfsvariable = A[minpos];
A[minpos] = A[j];
A[j] = hilfsvariable;
Das ganze machst du n-1 Mal, also 3*(n-1)
Lg
Thomas
LordNecro
04-11-2007, 15:00
Ich versteh auch nicht ganz was der Sinn des Beispiels ist, denn die Inputreihenfolge beim Selection-Sort hat keine Auswirkungen auf die Laufzeiten - vielleicht wollen sie genau das hören???
Ich denke mal das sie genau das hören wollen. Wenn man sich alte Bsp ansieht sieht man das sie das Beispiel schon öfter geben und immer mit nem anderen Verfahren. Wir hatten halt glück das wir das bekommen haben dem es egal ist wie die Eingabe aussieht. ;)
Zu den ausprogrammierten von Jacko:
Wenn du den Zähler dort reinprogrammiert hast wo ich glaube dann hast du folgende Situation:
Im allegemeinen benötigt jeder Datensatz eine Bewegung an seine Richtige Stelle( ich misch mich jetzt net ein in ob es 2-3 sind^^). Nur falls eine Zahl an der richtigen Stelle oder eine Zahl indirekt(d.h. Durch das Tauschen von 2 Zahlen beide auf ihren richtigen platz gelangen und damit die 2te sobald ihre position dran ist schon richtig steht) an die richtige stelle kommt überspringt das prog den Zähler. Darum kommst du manchmal auf weniger Bewegungen, was ja auch eigentlich richtig ist(es sei den man zählt mit sich selbst überschreiben als bewegung) Nichts desto trotz wirst du nie mehr bewegungen haben als n und darum = theta(n)
Ganz klar kann der Algorithmus für beliebige Eingaben nicht besser werden als der Best-Case
f_best(n) = ϴ(g(n)) ⇒ f(n) = Ω(g(n)).
Der Bests-Case ist mit der Abfrage "falls minpos > j dann" genau 0 und ohne diese Abfrage ϴ(n).
Welchen Fall sollen wir untersuchen, den mit der Abfrage, oder den ohne der Abfrage?
Kann es sein, dass im neuen Skriptum diese Abfrage gar nicht im Selection-Sort vorkommt? Rein theoretisch könnte für den Fall mit der Abfrage für die gegebene spezielle Eingabe etwas besseres als ϴ(n) rauskommen (was nicht der Fall ist, aber das muss ich erst begründen), auf jeden Fall gehen sich 0 Datenbewegungen nicht aus.
Ich denke mal das sie genau das hören wollen. Wenn man sich alte Bsp ansieht sieht man das sie das Beispiel schon öfter geben und immer mit nem anderen Verfahren. Wir hatten halt glück das wir das bekommen haben dem es egal ist wie die Eingabe aussieht. ;)
da bin ich aber mal gespannt! was die dazu sagen werden! ;)
Zu den ausprogrammierten von Jacko:
Wenn du den Zähler dort reinprogrammiert hast wo ich glaube dann hast du folgende Situation:
Im allegemeinen benötigt jeder Datensatz eine Bewegung an seine Richtige Stelle( ich misch mich jetzt net ein in ob es 2-3 sind^^). Nur falls eine Zahl an der richtigen Stelle oder eine Zahl indirekt(d.h. Durch das Tauschen von 2 Zahlen beide auf ihren richtigen platz gelangen und damit die 2te sobald ihre position dran ist schon richtig steht) an die richtige stelle kommt überspringt das prog den Zähler. Darum kommst du manchmal auf weniger Bewegungen, was ja auch eigentlich richtig ist(es sei den man zählt mit sich selbst überschreiben als bewegung) Nichts desto trotz wirst du nie mehr bewegungen haben als n und darum = theta(n)
falls es dich interessiert, das is der relevante codeteil von meinem selectionsort:
public static void selectionsort(int[] Folge, int n){
int vergleiche = 0;
int bewegungen = 0;
for(int j=0; j<n;j++){
printFolge(Folge);
int minpos = j;
for (int i = j+1;i<=n;i++){
vergleiche = vergleiche+1;
if(Folge[i] < Folge[minpos]){
minpos = i;
}
}
if(minpos>j){
bewegungen = bewegungen+1;
int tmp_a = Folge[minpos];
Folge[minpos] = Folge[j];
Folge[j] = tmp_a;
}
}
System.out.println("Vergleiche: "+vergleiche+" Bewegungen:"+bewegungen);
}
hoffe es hilft!
danke für die erklärung von dem 3*(n-1) jetzt is es mit klar!
ihr schreibt also jetzt als lösung Bewegungen: theta(n) Vergleiche: theta(n²)
und das die eingabefolge nichts an den theta werten ändert?
lg jacko
Jop, ich hab es so hingeschrieben, weil es bei Selection-Sort egal ist, wie die Eingabefolge aussieht.
Wenn jemand etwas Gegenteiliges behauptet, verweise ich auf Skriptum Seite 28 :-)
Lg
Thomas
hi
hab mir gerade selction sort durch geschaut und solange alle Schlüssel verschieden sind hat man immer (n*(n-1))/2 Vergleiche und n vertauschung
Und somit mit sind die Antworten für a und b gleich.
oder hab ich da was übersehen?
//edit ist doch nicht so einfach wie ich es mir gedacht habe. jetzt bei a) B=N-(N/4+) und bei b) für große N maximal B = N - 2 V sind bei beiden (N*(N-1)/2
lg spjoe
hi
//edit ist doch nicht so einfach wie ich es mir gedacht habe. jetzt bei a) B=N-(N/4+) und bei b) für große N maximal B = N - 2 V sind bei beiden (N*(N-1)/2
lg spjoe
kannst bitte erklären warum ist so? :confused:
michaelllll
06-11-2007, 21:42
Hat jemand schon ne Lösung für die Bewegungen im Beispiel b im Falle, wenn man die Zeile 9 nicht weglässt.
Lillipip
07-11-2007, 01:42
wenn ich lt. angabe N=8 annehme, dann komm ich mit den Vergleichen und der Formel N*(N-1)/2 = 28 Vergleiche... und wenn ich dann in die Formel mit der Hilfsvariable einsetze... 3(N-1) = 21 Bewegungen... Stimmt das so?
wenn ich lt. angabe N=8 annehme, dann komm ich mit den Vergleichen und der Formel N*(N-1)/2 = 28 Vergleiche... und wenn ich dann in die Formel mit der Hilfsvariable einsetze... 3(N-1) = 21 Bewegungen... Stimmt das so?
ja das is richtig so ....
für vergleich die Formel für Worst/Best/Avg aus dem Skriptum
=> theta n²
und für Bewegungen ebenfalls
3(n-1) für 3 Bewegungen => hilfvariable, umspeicherung, rückspeicherung
2(n-1) für 2 Bewegungen => umspeicherung, rückspeicherung
läuft beides aufs selbe raus theta n
;)
für eine Nichtsortierte Zahlenfolge stimmt die von mir geschriebene Laufzeit immer, Zeile 9 oder so wars glaub ich wenn man die weglässt stimmts auch für sotierte Zahlenfolgen
das Beispiel is echt nicht so schwer, da war das letztjährige deutlisch schwieriger, hier kann man sich direkt an den im Skriptum verwendeten Laufzeiten orientieren
Silent_Bob
07-11-2007, 16:41
Kann mir jemand die Funktion der Bediungung :
falls minpos > j dann
in Zeile 9 von Selection Sort im Skriptum Seite 28 erklären.
Das Minimum der unsortierten rechten Hälfe des Arrays muß doch ohnehin an den Anfang gesetzt werden, würde das dorch die Bedingung nicht verhindert werden, wenn j zB. A[1] und minpos A[4] ist.
Ich steh da grad auf der Leitung!
minpos gibt die aktuelle position des kleinsten elementes an
d.h. wenn es kein element gibt das kleiner ist als das zuerst ausgewählte dann wird hier logischerweiße keine vertauschung durchgeführt, da das element bereits richtig steht
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.