Datenelement: die kleinste Einheit, die ein Datenelement darstellt

Abstrakte Datenorganisation und damit verbundene Operationen

Vorteile: Es kann ein wahlfreier Zugriff erreicht werden und es wird weniger Speicherplatz benötigt

Nachteile: Es kann nur ein benachbarter Block von Speichereinheiten verwendet werden, was zu einer externen Fragmentierung führen kann

Vorteile: Keine Fragmentierung, volle Nutzung aller Speichereinheiten

Nachteile: Zeiger beanspruchen zusätzlichen Platz und können nur sequentiell zugreifen.

Vorteile: schnelle Abrufgeschwindigkeit

Nachteile: Die Indextabelle nimmt zusätzlichen Platz ein. Beim Hinzufügen oder Löschen von Daten muss die Indextabelle geändert werden, was zeitaufwändiger ist.

Vorteile: Das Abrufen, Hinzufügen und Löschen von Knoten erfolgt sehr schnell

Nachteile: Wenn die Hash-Funktion nicht gut ist, kann es zu Konflikten mit Elementspeichereinheiten kommen, die zusätzlichen Zeit- und Platzaufwand verursachen.

Weisen Sie für die logische Struktur auf die Funktion der Operation hin

Weisen Sie für die Speicherstruktur auf die spezifischen Arbeitsschritte der Operation hin

T(n) – Die Summe der Häufigkeiten aller Aussagen im Algorithmus

f(n) – die Häufigkeit grundlegender Operationen im Algorithmus

O – Größenordnung

Formeldefinition: Wenn T(n) und f(n) zwei Funktionen sind, die auf der Menge positiver Ganzzahlen definiert sind, dann gibt es positive Konstanten C und n0, so dass, wenn n>=n0, beide 0=<T(n) erfüllen. =<Cf(n)

Schlimmste Zeitkomplexität

durchschnittliche Zeitkomplexität

Beste Zeitkomplexität

a. Additionsregel

b. Multiplikationsregel