java algorithms collections

Java -Algorithmen und -Kollektionen

Benutzerdefinierte Datenerfassung für das technische Interview für die Rolle des Junior Java Developer.

Algorithmen

Sehen Sie hier die ganze Liste

Big O Notation

• Zeitkomplexität : Schätzung der Anzahl der Operationen oder Schritte, die ein Algorithmus als Funktion der Eingangsgröße ausgeführt werden muss.
• Raumkomplexität : Maximale Menge an Hilfsspeicher, die ein Algorithmus während seiner Ausführung als Funktion der Eingangsgröße zuordnen oder verwenden muss.
  • Hilfsraum ist der zusätzliche Raum oder den temporären Raum, der von einem Algorithmus verwendet wird.

n zeitkomplexität - die Anzahl der Elemente in der Eingabe.

n in der Raumkomplexität - Eingangsgröße in Einheiten von Bits, die zur Darstellung der Eingabe benötigt werden.

Big-O-Zeit-Komplexitätstabelle

Typ	Name	Erläuterung	Status	Beispiel
O(1)	Ständige Zeit	Der Algorithmus wird jedes Mal die gleiche Anzahl von Male ausgeführt, unabhängig von der Größe des Eingangs	Exzellent	Suche in einer Hash -Tabelle nach Schlüssel
O(log n)	Logarithmuszeit	Die Ausführungszeit steigt im Vergleich zur Erhöhung der Größe der Eingabedaten sehr langsam an	Exzellent	Binäre Suche (Durchschnitt)
O(n)	Lineare Zeit	Die Ausführungszeit ist linear proportional zur Größe der Eingabedaten	Gut	Brute Force -Suche
O(n + k)	Kombinierte/additive Zeit	Kombinierte Komplexität von zwei getrennten Eingängen	Gut	Zählsart
O(n log n)	Quasilinearzeit	Wenn die Eingangsgröße zunimmt	Schlecht	Sortierung zusammenführen, Haufensart
O(n^2)	Quadratische Zeit	Beinhaltet verschachtelte Iterationen oder Vergleiche für jedes Element	Schrecklich	Auswahlsart
O(2^n)	Exponentialzeit	Beinhaltet die umfassende Suche oder Aufzählung aller möglichen Kombinationen der Eingabe, die Ausführungszeit nimmt exponentiell zu	Schrecklich	TSP (Dynamische Programmierung)
O(n!)	Faktorielle Zeit	Beinhaltet die umfassende Suche oder Aufzählung aller möglichen Kombinationen der Eingabe, die Ausführungszeit nimmt faktorisch zu	Schrecklich	TSP (Brute Force)

Big-O-Raumkomplexitätstabelle

Typ	Name	Erläuterung	Status	Beispiel
O(1)	Konstanter Raum	Der Algorithmus erfordert eine feste Menge zusätzlicher Speicher, unabhängig von der Eingangsgröße	Exzellent	Haufensart
O(log n)	Logarithmischer Raum	Die Raumnutzung nimmt im Vergleich zur Zunahme der Größe der Eingabedaten langsam zu	Exzellent	Schnelle Sortierung
O(n)	Linearer Raum	Die Raumnutzung skaliert linear mit der Eingangsgröße	Gut	Sortierung zusammenführen
O(n + k)	Kombinierter/additiver Raum	Die Raumnutzung skaliert linear mit der Summe von n und k	Schlecht	Radix -Sortierung

Definitionen

Begriff	Definition	Beispiele
Abstrakter Datentyp (ADT)	Stellt eine hochrangige Beschreibung eines Datentyps dar, der sich eher auf sein Verhalten und seine Operationen als auf die spezifischen Implementierungsdetails konzentriert	Stack, Warteschlange, Wörterbuch, Sequenz, festgelegt
Datenstruktur	Technik oder Strategie zur Implementierung eines bestimmten Datentyps, Organisation und Speichern von Daten auf eine bestimmte Weise, um effiziente Vorgänge zu erleichtern	Array, verknüpfte Liste, Hash -Tabelle, Bäume (binärer Suchbaum, Haufen, rote/schwarze Bäume

Java -Sammlungsklassen

• Sammlung
  • Satz
    • Hashset
    • LinkedHashset
      • Sortiert
      • Navigableset
        • Treeset
  • Liste
    • ArrayList
    • LinkedList
    • Vektor
      • Stapel
  • Warteschlange
    • Prioritätswarteschlange
      • Deque
        • Arraydequeue
• Karte
  • Hashtable
  • Hashmap
  • LinkedHasMap
    • Sortiertmap
    • Navigablemap
      • Treemap

Vergleich von Sammlungstypen:

Typ	Doppelte Elemente	Reihenfolge der Elemente	Muss in bestimmter Reihenfolge hinzufügen/entfernen
Liste	Erlaubt	Nach Index	NEIN
Karte	Werte zulässig	Java verwendet den HashCode () des Schlüssels, um die Reihenfolge zu bestimmen. Für uns ist er nicht sortiert	NEIN
Warteschlange	Erlaubt	In definierter Reihenfolge abgerufen	Ja
Satz	Verboten	Nur in Treeset	Ja

Sammelattribute:

Typ	Schnittstelle	Sortiert?	Ruft hashCode() ?	Anrufe compareTo() ?
ArrayList	Liste	NEIN	NEIN	NEIN
LinkedList	Liste, Deque	NEIN	NEIN	NEIN
Arraydeque	Warteschlange, Deque	NEIN	NEIN	NEIN
Hashset	Satz	NEIN	Ja	NEIN
Treeset	Set, sortiert	Ja	NEIN	Ja
LinkedHashset	Satz	NEIN	Ja	NEIN
Hashmap	Karte	NEIN	Ja	NEIN
LinkedHasMap	Karte	NEIN	Ja	NEIN
Treemap	Karte, sortEdMap	Ja	NEIN	Ja

Die Datenstrukturen, die Sortierung beinhalten, erlauben keine Nullwerte.