Algo at Hochschule Karlsruhe | Flashcards & Summaries

Lernmaterialien für Algo an der Hochschule Karlsruhe

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Algo Kurs an der Hochschule Karlsruhe zu.

TESTE DEIN WISSEN

Direkte Auswahl Zeitaufwand

Lösung anzeigen
TESTE DEIN WISSEN

In jedem Fall Θ(n^2)

Lösung ausblenden
TESTE DEIN WISSEN

Binärsuche Zeitaufwand

Lösung anzeigen
TESTE DEIN WISSEN

Bester Fall: Z in der Mitte Θ(1)
Mittlerer Fall: Θ(logn)
Schlimmster Fall: Θ(logn)

Lösung ausblenden
TESTE DEIN WISSEN

Balancierte Suchbäume Erklärung

Lösung anzeigen
TESTE DEIN WISSEN

Schlimmster Fall aller Operationen auf Θ(log n) zu verbessern.

Dabei wird die höhe optimiert.

Ein binärer Suchbaum mit n Knoten ist dann balanciert, wenn die Höhe Θ(log n) beträgt.

Perfekt oder vollständig balanciert ist er, wenn jede Eben außer der untersten vollständig mit Knoten aufgefüllt ist.

Lösung ausblenden
TESTE DEIN WISSEN

Stack Laufzeit

Lösung anzeigen
TESTE DEIN WISSEN

Operationen Θ(1)
Erzeugen Θ(n)

Lösung ausblenden
TESTE DEIN WISSEN

Minimumsuche Erklärung

Lösung anzeigen
TESTE DEIN WISSEN

Sequentiell kleinsten Wert suchen.

In der Schleife den aktuellen Wert von a[minindex] mit dem nächsten Wert vergleichen.

Lösung ausblenden
TESTE DEIN WISSEN

Minimumsuche Zeitaufwand

Lösung anzeigen
TESTE DEIN WISSEN

In jedem Fall Θ(n)

Lösung ausblenden
TESTE DEIN WISSEN

Bubblesort Laufzeit

Lösung anzeigen
TESTE DEIN WISSEN

Θ(n^2)

Lösung ausblenden
TESTE DEIN WISSEN

Heapsort Laufzeit

Lösung anzeigen
TESTE DEIN WISSEN
  1. In jedem Fall Θ(n log n)

Lösung ausblenden
TESTE DEIN WISSEN

Stabile Verfahren

Lösung anzeigen
TESTE DEIN WISSEN

Direktes Einfügen

Mergesort

Bubblesort

Lösung ausblenden
TESTE DEIN WISSEN

Minimumsuche Korrektheit

Lösung anzeigen
TESTE DEIN WISSEN

Terminiert: 

Anzahl Schleifendurchläufe unabhängig Werte a => n-1


Schleifeninvariante :

  • Eintritt Schleife,da 

a[minindex] = a[start]

  • Fortführung Schleife

  •  true:

  Vor der Zuweisung gilt a[i] ≤ a[minindex] danach

  a[minindex ] = min.length

  • false:

  •  gilt a[minindex] < a[i] und damit die Invariante.

  •  Korrektheit:

  • Invariante nach Terminierung:

 a[minindex] = min{a[start], . . . , a[n − 1]}

Lösung ausblenden
TESTE DEIN WISSEN

Direkte Auswahl Beschreibung    

Lösung anzeigen
TESTE DEIN WISSEN

Einteilung in zwei Bereiche sortiert und unsortiert.

Aus unsortierten Bereich kleinste Wert a[k] gewählt und mit a[i] getauscht.
Zu beginn a[i] = 0
Lösung ausblenden
TESTE DEIN WISSEN

Lineare Suche Zeitaufwand

Lösung anzeigen
TESTE DEIN WISSEN

Jeder Wert genau.
In jedem Fall Θ(n)

Lösung ausblenden
  • 33832 Karteikarten
  • 923 Studierende
  • 59 Lernmaterialien

Beispielhafte Karteikarten für deinen Algo Kurs an der Hochschule Karlsruhe - von Kommilitonen auf StudySmarter erstellt!

Q:

Direkte Auswahl Zeitaufwand

A:

In jedem Fall Θ(n^2)

Q:

Binärsuche Zeitaufwand

A:

Bester Fall: Z in der Mitte Θ(1)
Mittlerer Fall: Θ(logn)
Schlimmster Fall: Θ(logn)

Q:

Balancierte Suchbäume Erklärung

A:

Schlimmster Fall aller Operationen auf Θ(log n) zu verbessern.

Dabei wird die höhe optimiert.

Ein binärer Suchbaum mit n Knoten ist dann balanciert, wenn die Höhe Θ(log n) beträgt.

Perfekt oder vollständig balanciert ist er, wenn jede Eben außer der untersten vollständig mit Knoten aufgefüllt ist.

Q:

Stack Laufzeit

A:

Operationen Θ(1)
Erzeugen Θ(n)

Q:

Minimumsuche Erklärung

A:

Sequentiell kleinsten Wert suchen.

In der Schleife den aktuellen Wert von a[minindex] mit dem nächsten Wert vergleichen.

Mehr Karteikarten anzeigen
Q:

Minimumsuche Zeitaufwand

A:

In jedem Fall Θ(n)

Q:

Bubblesort Laufzeit

A:

Θ(n^2)

Q:

Heapsort Laufzeit

A:
  1. In jedem Fall Θ(n log n)

Q:

Stabile Verfahren

A:

Direktes Einfügen

Mergesort

Bubblesort

Q:

Minimumsuche Korrektheit

A:

Terminiert: 

Anzahl Schleifendurchläufe unabhängig Werte a => n-1


Schleifeninvariante :

  • Eintritt Schleife,da 

a[minindex] = a[start]

  • Fortführung Schleife

  •  true:

  Vor der Zuweisung gilt a[i] ≤ a[minindex] danach

  a[minindex ] = min.length

  • false:

  •  gilt a[minindex] < a[i] und damit die Invariante.

  •  Korrektheit:

  • Invariante nach Terminierung:

 a[minindex] = min{a[start], . . . , a[n − 1]}

Q:

Direkte Auswahl Beschreibung    

A:

Einteilung in zwei Bereiche sortiert und unsortiert.

Aus unsortierten Bereich kleinste Wert a[k] gewählt und mit a[i] getauscht.
Zu beginn a[i] = 0
Q:

Lineare Suche Zeitaufwand

A:

Jeder Wert genau.
In jedem Fall Θ(n)

Algo

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang Algo an der Hochschule Karlsruhe

Für deinen Studiengang Algo an der Hochschule Karlsruhe gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Algo
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Algo