Testangabe

  • für alle, die nicht da waren:
    testangaben, soweit ich sie mir gemerkt hab:


    1.a) zeigen oder widerlegen:
    f(n) = O(g(n)²) => f(n) = Omega(g(n)


    1.b) f(n) = { n³ - 0.3n² + 2.7n für n >= 1000
    n^4 für n<1000
    zeigen oder widerlegen: f(n) = Theta(n³)



    2.a) <12,55,3,66,54,552> (kA, beliebige folge eben)
    selection sort durchführen


    2.b1) gegeben: absteigend soriterte folge
    ist insertion oder merge sort bessser, wenn die ausgabe auch absteigend sortiert sein soll? angabe mittels Theta
    2.b2) gesucht: av.Zeitaufwand für insert&merge


    3.a) gegeben: absteigend sortierte doppelt verkettete zyklische liste.
    gesucht: algo zum einfügen eines elementes incl. skizze


    3.b) Theta notation für diesen algorithmus im best, worst und av. case


    a.A.o.G


    lg peter

  • bei meiner Gruppe wars:
    1.a) Zeige/wiederlege
    f(n) = Theta(n^4)
    f(n) = n^4________für n prim
    _____n^4-nlogn___für n nicht prim
    1.b) Zeige/wiederlege aus f(n) = Sigma(g(n)) folgt f(n) = O(2g(n))
    2.a) irgendeine Folge mittels Insertionsort sortieren
    2.b) Was bedeutet stabil bei Sortierverfahren, sind Quicksort und Selectionsort stabil/warum ja/nicht
    3.a) einfügen eines Elementes an die richtige Stelle in einer aufsteigend sortierten eínfach verketteten Liste in Pseudocode schreiben
    3.b) Laufzeit davon für Bestcase/WorstCase/AvgCase in Theta Notation