Wie ist das zeitliche Ergebnis der Operationen Einfügen, Suchen, Lesen und Löschen von Elementen in einem Array im schlimmsten und durchschnittlichen Fall?

Für ein Standard-Array in iOS (z.B. NSArray oder NSMutableArray) sind die zeitlichen Eigenschaften der Operationen ungefähr wie folgt:

• Einfügen:

  • Am Ende des Arrays (append): Durchschnitts- und Worst-Case — O(1) amortisiert (wenn keine Speicherneuordnung erforderlich ist).
  • Am Anfang oder in der Mitte: O(n), da die Elemente verschoben werden müssen.

• Suche (bei Indexsuche): O(1), da das Array indiziert ist.

• Lesen nach Index: O(1).

• Löschen:

  • Vom Ende des Arrays: O(1).
  • Vom Anfang oder in der Mitte: O(n), aufgrund des Verschiebens der Elemente.

Daher haben Operationen zum Einfügen und Löschen in der Mitte oder am Anfang des Arrays eine lineare Komplexität, während der Zugriff und das Einfügen/Löschen am Ende konstant sind (amortisiert).