Algorythmen und Komplexität an der Beuth Hochschule für Technik

Karteikarten und Zusammenfassungen für Algorythmen und Komplexität an der Beuth Hochschule für Technik

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 Algorythmen und Komplexität an der Beuth Hochschule für Technik.

Beispielhafte Karteikarten für Algorythmen und Komplexität an der Beuth Hochschule für Technik auf StudySmarter:

Linearsuche
Günstigster Fall
Schlechstester Fall
Durchschnittsfall

Beispielhafte Karteikarten für Algorythmen und Komplexität an der Beuth Hochschule für Technik auf StudySmarter:

Vorraussetzungen Binärsuche

Beispielhafte Karteikarten für Algorythmen und Komplexität an der Beuth Hochschule für Technik auf StudySmarter:

Binärsuche Laufzeiten GF DF SF

Beispielhafte Karteikarten für Algorythmen und Komplexität an der Beuth Hochschule für Technik auf StudySmarter:

Eine zeige Mittels Induktion aufgabe

Beispielhafte Karteikarten für Algorythmen und Komplexität an der Beuth Hochschule für Technik auf StudySmarter:

Sortierverfahren Unterscheidung

Beispielhafte Karteikarten für Algorythmen und Komplexität an der Beuth Hochschule für Technik auf StudySmarter:

Insertion Sort

Beispielhafte Karteikarten für Algorythmen und Komplexität an der Beuth Hochschule für Technik auf StudySmarter:

Inesrtion Sort Aufwand

Beispielhafte Karteikarten für Algorythmen und Komplexität an der Beuth Hochschule für Technik auf StudySmarter:

BubbleSort

Beispielhafte Karteikarten für Algorythmen und Komplexität an der Beuth Hochschule für Technik auf StudySmarter:

Aufwand BubbleSort

Beispielhafte Karteikarten für Algorythmen und Komplexität an der Beuth Hochschule für Technik auf StudySmarter:

Optimierung BubbleSort

Beispielhafte Karteikarten für Algorythmen und Komplexität an der Beuth Hochschule für Technik auf StudySmarter:

Mergesort Optimierung

Beispielhafte Karteikarten für Algorythmen und Komplexität an der Beuth Hochschule für Technik auf StudySmarter:

Mergesort

Kommilitonen im Kurs Algorythmen und Komplexität an der Beuth Hochschule für Technik. 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 Algorythmen und Komplexität an der Beuth Hochschule für Technik auf StudySmarter:

Algorythmen und Komplexität

Linearsuche
Günstigster Fall
Schlechstester Fall
Durchschnittsfall

GF: 1
DF = n/2
SF = n

Algorythmen und Komplexität

Vorraussetzungen Binärsuche

Aufsteigend/absteigende Sortierung
Vergleiche Element mit Mitte des Suchbereiches
Falls gefunden Mitte return
Else falls kleiner suche links bis mitte -1
Else falls größer suche mitte+1 bis rechts

Algorythmen und Komplexität

Binärsuche Laufzeiten GF DF SF

GF = 1
DF = (log n)
SF = (log n)

gleichung: f(n/2)+1

Algorythmen und Komplexität

Eine zeige Mittels Induktion aufgabe

Füg mal ein bitte

Algorythmen und Komplexität

Sortierverfahren Unterscheidung

Laufzeiteffizient (Best, Average and Worstcase), Speicherplatzeffizienz (in place, out of place), Stabilität (Änderung der Reihenfolge von Elementen mit gleichen Schlüsseln)

Algorythmen und Komplexität

Insertion Sort

Jedes Element an sich betrachtet. Größere Elemente werden nach rechts geschoben.

Algorythmen und Komplexität

Inesrtion Sort Aufwand

Abhängig von Anzahl Feldelemente, abhängig von Anordnung im Feld
GF : n-1 VGL
SF: Feld absteigend Sortiert (n^2/2)
DF: n^2/4
Liegt in O(n^2)
Iterativ, nciht rekursiv. Stabil ( benachbarte Schlüssel werden nicht getauscht, in place - kein zusätzlicher Speicheraufwand)
Eignet sich für kleinere Eingabemengen, für vorsortierte Mengen,
Optimierung: Wächterelement für die While Schleife
Nutzung der binären Suche reduziert Vergleiche, aber nicht die Verschiebungen im Array

Algorythmen und Komplexität

BubbleSort

Durchlaufe ein Feld und vertrausche benachbarte Elemente falls notwendig.
Wenn nicht mehr notwendig => Feld sortiert

Algorythmen und Komplexität

Aufwand BubbleSort

Abhängig von der Feldlänge und Anordnung der Element im Feld
GF: N - Alles sortiert
SF: Feld absteigend sortiert = n^2/2
Durchschnittlicher Fall = n^2/4
Aufwand O(n^2)

Iterativ, nicht rekursiv,
Stabil, benahcbarte werden nicht getauscht, inplace - kein zusätzlicher Speicheraufwand

Algorythmen und Komplexität

Optimierung BubbleSort

Ersetzen der äußeren Schleife durch while shcleife -im günstigsten Fall O(n)
Feld abwechselnd von oben und unten durchlaufen
Praxis: Nur für vorsortierte Mengen ode rkleine Eingabemengen - Insertionsort schneller

Algorythmen und Komplexität

Mergesort Optimierung

Nutzung von InsertionSort für kleine Elemente
Bei partiell sortierten Feldern - kein Merge notwendig
Einsparung der Befüllung des Hilfsfeldes

Algorythmen und Komplexität

Mergesort

 Rekursiv, stabil (Benachbarte Schlüssel werden nicht getauscht - je nach implementierung in place oder zusätzlicher Speicheraufwand von O(n) oder O(n logn)

Beste nd schlechteste Laufzeit O(n log n)
Aufteilung in zwei gleichgroße Zeilprobleme

Melde dich jetzt kostenfrei an um alle Karteikarten und Zusammenfassungen für Algorythmen und Komplexität an der Beuth Hochschule für Technik zu sehen

Singup Image Singup Image
Wave

Andere Kurse aus deinem Studiengang

Für deinen Studiengang Algorythmen und Komplexität an der Beuth Hochschule für Technik gibt es bereits viele Kurse auf StudySmarter, denen du beitreten kannst. Karteikarten, Zusammenfassungen und vieles mehr warten auf dich.

Zurück zur Beuth Hochschule für Technik Ü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 Algorythmen und Komplexität an der Beuth Hochschule für Technik 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

Guten 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