Suchen-Sortieren-Bäume an der Universität Potsdam

Karteikarten und Zusammenfassungen für Suchen-Sortieren-Bäume an der Universität Potsdam

Arrow Arrow

Komplett kostenfrei

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

Lerne jetzt mit Karteikarten und Zusammenfassungen für den Kurs Suchen-Sortieren-Bäume an der Universität Potsdam.

Beispielhafte Karteikarten für Suchen-Sortieren-Bäume an der Universität Potsdam auf StudySmarter:

Lineare Suche,
Binäre Suche

Beispielhafte Karteikarten für Suchen-Sortieren-Bäume an der Universität Potsdam auf StudySmarter:

Selection Sort

Beispielhafte Karteikarten für Suchen-Sortieren-Bäume an der Universität Potsdam auf StudySmarter:

In-place Algorithmus
Das war nur eine Vorschau der Karteikarten auf StudySmarter.
Flascard Icon Flascard Icon

Über 50 Mio Karteikarten von Schülern erstellt

Flascard Icon Flascard Icon

Erstelle eigene Karteikarten in Rekordzeit

Flascard Icon Flascard Icon

Kostenlose Karteikarten zu STARK Inhalten

Kostenlos anmelden

Beispielhafte Karteikarten für Suchen-Sortieren-Bäume an der Universität Potsdam auf StudySmarter:

Insertion Sort
als In-place

Beispielhafte Karteikarten für Suchen-Sortieren-Bäume an der Universität Potsdam auf StudySmarter:

Mergesort

Beispielhafte Karteikarten für Suchen-Sortieren-Bäume an der Universität Potsdam auf StudySmarter:

Quicksort

Beispielhafte Karteikarten für Suchen-Sortieren-Bäume an der Universität Potsdam auf StudySmarter:

Entscheidungsbaum
Das war nur eine Vorschau der Karteikarten auf StudySmarter.
Flascard Icon Flascard Icon

Über 50 Mio Karteikarten von Schülern erstellt

Flascard Icon Flascard Icon

Erstelle eigene Karteikarten in Rekordzeit

Flascard Icon Flascard Icon

Kostenlose Karteikarten zu STARK Inhalten

Kostenlos anmelden

Beispielhafte Karteikarten für Suchen-Sortieren-Bäume an der Universität Potsdam auf StudySmarter:

Baum

Beispielhafte Karteikarten für Suchen-Sortieren-Bäume an der Universität Potsdam auf StudySmarter:

Tiefe

Beispielhafte Karteikarten für Suchen-Sortieren-Bäume an der Universität Potsdam auf StudySmarter:

Wald

Beispielhafte Karteikarten für Suchen-Sortieren-Bäume an der Universität Potsdam auf StudySmarter:

Aufspannender Baum
Das war nur eine Vorschau der Karteikarten auf StudySmarter.
Flascard Icon Flascard Icon

Über 50 Mio Karteikarten von Schülern erstellt

Flascard Icon Flascard Icon

Erstelle eigene Karteikarten in Rekordzeit

Flascard Icon Flascard Icon

Kostenlose Karteikarten zu STARK Inhalten

Kostenlos anmelden

Beispielhafte Karteikarten für Suchen-Sortieren-Bäume an der Universität Potsdam auf StudySmarter:

Binärer Baum

Kommilitonen im Kurs Suchen-Sortieren-Bäume an der Universität Potsdam. erstellen und teilen Zusammenfassungen, Karteikarten, Lernpläne und andere Lernmaterialien mit der intelligenten StudySmarter Lernapp. Jetzt mitmachen!

Jetzt mitmachen!

Flashcard Flashcard

Beispielhafte Karteikarten für Suchen-Sortieren-Bäume an der Universität Potsdam auf StudySmarter:

Suchen-Sortieren-Bäume

Lineare Suche,
Binäre Suche
Linear:
- Durchsuchen von vorne bis hinten.
-> O(n)

Binär:
- Liste muss sortiert sein.
- Untersuchung es Elem. in der Mitte.

-> falls kein Treffer erzielt wurde,
     teile die Liste in Hälften.
-> suche in der passenden
     Teilliste weiter.

- Suche verläuft Rekursiv.
-> O(log n)

Suchen-Sortieren-Bäume

Selection Sort
In-place Algorithmus.
Jeden Index mit allen davon
rechteren Indizes vergleichen.

-> Austausch, falls ausgewählter
     Index größer als der rechtere.

-> O(n^2)

Suchen-Sortieren-Bäume

In-place Algorithmus
Prozedur, die Eingabedaten
im Speicher direkt manipuliert.

-> kein weiterer Speicherbedarf.
-> Nebeneffekt an Eingabedaten.

Suchen-Sortieren-Bäume

Insertion Sort
als In-place
Rückwärtiges Durchsuchen
nach korrekter Position für
den ausgewählten Index.

-> vom 2. Element bis zum letzten
     jeweils mit dessen linkeren
     Elementen vergleichen und
     bei Bedarf tauschen.

-> O(n^2)

Suchen-Sortieren-Bäume

Mergesort
kein In-place Algorithmus.
Zusammenmischen von sortierten
Teilfolgen, die davor in Sequenzen
der Länge 1 unterteilt wurden.

- rekursives Vorgehen
- Zusammensetzen: lineare Laufzeit.
-> günstig für viele, verschiedene Folgen.

-> O(n log n)

Suchen-Sortieren-Bäume

Quicksort
In-place Algorithmus.
Sortieren durch Teilen der Liste
in zwei Teilfolgen unter Auswahl
des Pivot-Elements, mit welchem
alle anderen Elemente verglichen
werden.

Teilfolge1:  alle Elem.   <   Pivot.
Teilfolge2: alle Elem.  >=  Pivot.

- in der teile(L, low, high) Funktion
   mit zwei Laufvariablen von
   Außen nach Innen arbeiten und 
   Seitentausch, wenn Element
   auf falscher Seite ist. Sonst weiter
   nach innen vordringen.

- Lösung: die sortierten Teilfolgen
   konkatenieren.
- kein Mischen erforderlich.
-> in der Praxis oft überlegen.

Suchen-Sortieren-Bäume

Entscheidungsbaum
Die Anzahl der Entscheidungen
ist für jede Anordnung der Abstand
des Blattes von der Wurzel.

-> maximal: die Tiefe des Baums.
(Anzahl der Ebenen -1)

- für Folge mit Länge n:
   n! verschiedene Anordnungen.

für Sortieralgorithmen:
-> Binärer Baum.

Suchen-Sortieren-Bäume

Baum
Zusammenhängender,
kreisfreier Graph.

Wurzel:
Knoten ohne Vater.
Blatt:
Knoten ohne Kinder.
Innerer Knoten:
Knoten zwischen Wurzel u. Blättern.

Suchen-Sortieren-Bäume

Tiefe
Tiefe eines Knotens:
Abstand von der Wurzel
zum Knoten.

Tiefe des Baums:
Größter Abstand von der
Wurzel zu einem Blatt.

:= max{tiefe(v,T): v ist Blatt}

Suchen-Sortieren-Bäume

Wald
Kreisfreier Graph.

-> hat Bäume als
     Zusammenhangs-
     komponenten.

Suchen-Sortieren-Bäume

Aufspannender Baum
Teilgraph eines Graphen G,
der ein Baum ist und alle
Knoten von G enthält.

Suchen-Sortieren-Bäume

Binärer Baum
Ausgangsgrad jedes Knotens
des Baums ist höchstens 2.

- Tiefe d:
-> max. 2^d Blätter.
-> max. 2^(d+1) -1 Knoten.

Melde dich jetzt kostenfrei an um alle Karteikarten und Zusammenfassungen für Suchen-Sortieren-Bäume an der Universität Potsdam zu sehen

Singup Image Singup Image
Wave

Andere Kurse aus deinem Studiengang

Für deinen Studiengang Suchen-Sortieren-Bäume an der Universität Potsdam gibt es bereits viele Kurse auf StudySmarter, denen du beitreten kannst. Karteikarten, Zusammenfassungen und vieles mehr warten auf dich.

Zurück zur Universität Potsdam Übersichtsseite

Assembler, Interpreter/Compiler

2er Potenzen

Algorithmische Konzepte

Menschen, Betriebe, soziale Systeme an der

Universität Hohenheim

Streuselkuchen an der

Universität des Saarlandes

Sucht an der

SRH Hochschule für Gesundheit

Menschen, Tiere und Pflanzen in ihren Lebensräumen an der

Bergische Universität Wuppertal

Tauchen an der

Deutsche Sporthochschule Köln

Ähnliche Kurse an anderen Unis

Schau dir doch auch Suchen-Sortieren-Bäume an anderen Unis an

Zurück zur Universität Potsdam Übersichtsseite

Was ist StudySmarter?

Was ist StudySmarter?

StudySmarter ist eine intelligente Lernapp für Studenten. Mit StudySmarter kannst du dir effizient und spielerisch Karteikarten, Zusammenfassungen, Mind-Maps, Lernpläne und mehr erstellen. Erstelle deine eigenen Karteikarten z.B. für Suchen-Sortieren-Bäume an der Universität Potsdam oder greife auf tausende Lernmaterialien deiner Kommilitonen zu. Egal, ob an deiner Uni oder an anderen Universitäten. Hunderttausende Studierende bereiten sich mit StudySmarter effizient auf ihre Klausuren vor. Erhältlich auf Web, Android & iOS. Komplett kostenfrei. Keine Haken.

Awards

Bestes EdTech Startup in Deutschland

Awards
Awards

European Youth Award in Smart Learning

Awards
Awards

Bestes EdTech Startup in Europa

Awards
Awards

Bestes EdTech Startup in Deutschland

Awards
Awards

European Youth Award in Smart Learning

Awards
Awards

Bestes EdTech Startup in Europa

Awards
X

StudySmarter - Die Lernplattform für Studenten

StudySmarter

4.5 Stars 1100 Bewertungen
Jetzt entdecken
X

Gute Noten in der Uni? Kein Problem mit StudySmarter!

89% der StudySmarter Nutzer bekommen bessere Noten in der Uni.

50 Mio Karteikarten & Zusammenfassungen
Erstelle eigene Lerninhalte mit Smart Tools
Individueller Lernplan & Statistiken


Lerne mit über 1 Millionen Nutzern in der kostenlosen StudySmarter App.

Du bist schon registriert? Hier geht‘s zum Login