Posts by Kitty

Ich komme auf

Sqrt(8,n) X _ _ _
log(8,n) _ _ _ X
1/log(8,n)) _ X _ _

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

und wieso kann mein Ergebnis bei 4) nicht stimmen?

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

weiss nicht, steht bei mir auch da, dürfte wohl normal sein

hast du Algorithmen und Datenstrukturen 1 UE abonniert? Wenn ja dann muss bei Abonnierte LVAs neben Algorithmen und Datenstrukturen 1 UE --> G stehen

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.

Bei Abonnierte LVAs steht dann neben Algorithmen und Datenstrukturen 1 UE --> G. Da müsst ihr drauflicken.

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.

Ist a* nicht auch nur ein Zustand und {ε} hat doch 2 Zustände oder?

ich würde die mitschrift auch brauchen

edit: blödsinn

es kommt ja log n heraus

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.

naja aber für große n ( n > 10) wächst n nun mal langsamer als n log n

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.

naja n wächst langsamer als n log n

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