Zeitkomplexität von Datenstrukturen

Question

Ich wollte über this page:

Und ich hatte die folgenden Fragen:

1. Does Einfügen und Löschen in dieser Tabelle bedeutet das Einfügen und Löschen in der nur enden?

2. Warum wird für Basic Array das Einfügen und Löschen für den Durchschnitts- und Worst Case als - markiert?

3. Was bedeutet Indexierung in der Tabelle? Bedeutet es Zugriff?

4. Warum wird das dynamische Array O (n) eingefügt und gelöscht?

5. Warum ist der Index der verknüpften Liste O (n) während der von Dynamic Array O (1)? Liegt es daran, dass das dynamische Array kontinuierlich ist und direkt durch Zeigerarithmetik aufgerufen werden kann, während für eine verknüpfte Liste eine lineare Suche erforderlich wäre?

Answer 1

1. Does Einfügen und Löschen in dieser Tabelle nur das Einfügen und Löschen am Ende bedeuten?

   Nein. Diese reflektieren zufälliges Einfügen und Löschen.

---

2. nach Wesentlichen Array, warum ist das Einfügen und Löschen für mittleren und schlimmstenfalls als - markiert?

   Weil "Basic Array" eine statische Array-Struktur ist. Sie können keine Elemente einfügen oder löschen.

---

3. Was in der Tabelle bedeutet Indexierung? Bedeutet es Zugriff?

   Es bedeutet: Zugriff nach Index (Position) im Gegensatz zum Zugriff per Schlüssel.

---

4. Warum ist das Einfügen und Löschen von Dynamic Array O (n)?

   Da das Einfügen/Löschen möglicherweise erfordert, dass das Array in der Länge wächst oder schrumpft. Dies kann das Kopieren von (allen) Elementen beinhalten. Daher O (N).

---

5. Warum ist der Index der verknüpften Liste O (n), während die von Dynamic Array O (1)? Liegt es daran, dass das dynamische Array kontinuierlich ist und direkt durch Zeigerarithmetik aufgerufen werden kann, während für eine verknüpfte Liste eine lineare Suche erforderlich wäre?

   Ja.

Answer 2

Für 4, wenn Sie ein Element in oder aus einem D-Array einfügen oder löschen, sollten Sie den Index angeben, einfügen oder löschen, so müssen Sie einige Elemente machen vorwärts oder rückwärts