Posts by Kitty

    wie kommt ihr darauf dass es bei 1) nur nur eine untere Schranke gibt? Ich kann da nur eine obere Schranke angeben

    also bei 3) hab ich jetzt n, |_k/2_|

    bei 4) habe ich deswegen n² und m gewählt, weil die innere schleife zwar beim ersten mal n² mal dürchgeführt wird aber beim zweiten mal nur mehr n²/2, dann n²/4, also n²+n²/2+n²/4+.... diese Summe konvergiert gegen 2n², was dann ja theta(n²) ist.

    bei 1) hab ich n,m/3
    bei 2) hab ich s-1
    bei 3) hab ich 15(beliebige zahl nehmen), k/2
    bei 4) hab ich n², m

    Ich habe mich so angemeldet. Wenn ihr auf --> G klickt kommt ihr auf eine Seite wo die genauen Zeiten und Orte stehen und oben links wählt ihr dann nur mehr die Gruppennummer aus.

    Du musst nochmal 53 abziehen, da wenn jemand alle drei Artikel benutzt, dann wird er sowohl bei a n b, b n c als auch bei a n c mitgezählt, also 3 mal, also musst du a n b n c 2 mal abziehen, damit der jeweilige Haushalt wirklich nur einmal gezählt wird.

    Wenn du 3x A n B n C abziehst, dann kommen aber nur jene Haushalte heraus die genau 2 Artikel benutzen, Meiner Meinung nach gehört eher nur 2x A n B n C abgezogen, um die Anzahl der Haushalte welche mindestens 2 Artikel benutzen zu berechnen.

    1.3) iii) kann nicht n/2 sein, denn es wird ja nicht nur einmal durch 2 dividiert, sondern solange bis m <= 0 ist. Die für schleife ist da nicht zu beachten, aber die wiederhole bis schleife schon, denn da kommt m = n ja vor.

    Also so wie ich den Satz am Übungsblatt verstehe geht es genau darum, dass gleiche Elemente nach dem sortieren noch in der selben Reihenfolge sein sollen.

    Im konkreten Fall (aufsteigend sortiert --> aufsteigend sortiert) ist also Insertion Sort schneller, im Durchschnitt ist aber Merge Sort schneller.