Testangabe

[moose]

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

[Zentor]

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

[#!/usr/bin/perl]

meinst du nicht einfach verkettet statt einelementig?

[Zentor]

oh, natürlich, sorry habs schon oben ausgebessert
mfg Zentor