wake-up-neo.com

Was ist die zeitliche Komplexität des Indizierens, Einfügens und Entfernens von gemeinsamen Datenstrukturen?

Es gibt keine Zusammenfassung der großen O-Notation für Operationen mit den gängigsten Datenstrukturen, einschließlich Arrays, verknüpften Listen, Hash-Tabellen usw.

30
James

Informationen zu diesem Thema finden Sie jetzt auf Wikipedia unter: Datenstruktur durchsuchen

+----------------------+----------+------------+----------+--------------+
|                      |  Insert  |   Delete   |  Search  | Space Usage  |
+----------------------+----------+------------+----------+--------------+
| Unsorted array       | O(1)     | O(1)       | O(n)     | O(n)         |
| Value-indexed array  | O(1)     | O(1)       | O(1)     | O(n)         |
| Sorted array         | O(n)     | O(n)       | O(log n) | O(n)         |
| Unsorted linked list | O(1)*    | O(1)*      | O(n)     | O(n)         |
| Sorted linked list   | O(n)*    | O(1)*      | O(n)     | O(n)         |
| Balanced binary tree | O(log n) | O(log n)   | O(log n) | O(n)         |
| Heap                 | O(log n) | O(log n)** | O(n)     | O(n)         |
| Hash table           | O(1)     | O(1)       | O(1)     | O(n)         |
+----------------------+----------+------------+----------+--------------+

 * The cost to add or delete an element into a known location in the list (i.e. if you have an iterator to the location) is O(1). If you don't know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time. 
** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element.
65
Mobiletainment

Denken Sie daran, dass die Implementierung von Datenstrukturen in der Sprache/dem Framework Ihrer Wahl erheblich davon abhängen kann, ob Sie eine eigene Datenstruktur schreiben (z. B. eine verknüpfte Liste in C). Schauen Sie sich zum Beispiel die Benchmarks von Apples CFArray bei Ridiculous Fish an . In diesem Fall ändert der Datentyp, ein CFArray aus dem CoreFoundation-Framework von Apple, die Datenstruktur in Abhängigkeit davon, wie viele Objekte sich tatsächlich im Array befinden - von linearer Zeit zu konstanter Zeit bei etwa 30.000 Objekten.

Dies ist tatsächlich eines der schönsten Dinge bei der objektorientierten Programmierung - Sie müssen nicht wissen , wie es funktioniert, sondern nur dass es funktioniert, und das 'wie es funktioniert' kann sich je nach Anforderungen ändern.

4
Dan Udey

Nichts ist so nützlich wie dieses: Allgemeine Datenstrukturoperationen :

enter image description here

2
Pritam Banerjee

Rot-schwarze Bäume:

  • Einfügen - O (log n)
  • Abrufen - O (log n)
  • Löschen - O (log n)
2
Hank Gay

Amortisiertes Big-O für Hashtables:

  • Einfügen - O (1)
  • Abrufen - O (1)
  • Löschen - O (1)

Beachten Sie, dass es einen konstanten Faktor für den Hashing-Algorithmus gibt und die Abschreibung bedeutet, dass die tatsächlich gemessene Leistung dramatisch variieren kann.

1
Hank Gay