Drucken

Informatik (M.Sc.)

Diese Seiten können nicht richtig dargestellt werden, da Sie Ihren Internet Explorer mit aktivierter Kompatibiltätsansicht verwenden. Wir empfehlen 'fu-berlin.de' aus der Liste der Websites mit aktivierter Kompatibilitätsansicht zu entfernen:

  1. Blenden Sie bitte in Ihrem Internet Explorer die Menüleiste ein, indem Sie entweder 'Alt' drücken oder in der Adressleiste mit der rechten Maustaste klicken und dann 'Menüleiste' auswählen.
  2. Klicken Sie auf 'Extras' und wählen das Menü 'Einstellungen der Kompatibilitätsansicht' aus.
  3. Wählen Sie unter 'Zur Kompatibilitätsansicht hinzugefügte Websites' 'fu-berlin.de' aus.
  4. Klicken Sie auf 'Entfernen'.

Worst-Case-Laufzeiten von Sortierverfahren - Theoretische Informatik

Sortierverfahren sind häufige, in der Informatik vorkommende Algorithmen.

Unten stehende Matrix zeigt Ihnen eine Auswahl von diesen Sortierverfahren. Ihre Aufgabe sei es, diese Verfahren anhand der gegebenen asymptotischen Schranken in Kategorien einzuteilen. Sortieren Sie hierbei bitte der nach der Worst-Case-Laufzeit, also dem schlechtest möglichen Fall.

Mit einem Klick auf die Schaltfläche Ergebnis können Sie Ihre Eingabe überprüfen.

O(n)

O(n log n)

O(n1,25)

O(n2)

O(n2,71)

Quicksort

Bubblesort

Mergesort

Shellsort

Stoogesort

Sowohl Quicksort als auch Bubblesort haben im Worst-Case eine asymptotische Laufzeit von O(n2). Mergesort arbeitet effizienter und hat eine obere Schranke von O(n log n). Shellsort (O(n1,25)) und Stoogesort (O(n2,71)) sind eher in exotischen Laufzeitkategorien zu finden.