Er is geen samenvatting beschikbaar van de grote O-notatie voor operaties op de meest voorkomende gegevensstructuren, waaronder arrays, gekoppelde lijsten, hash-tabellen enz.
Antwoord 1, Autoriteit 100%
Informatie over dit onderwerp is nu beschikbaar op Wikipedia op: zoekgegevensstructuur
+----------------------+----------+------------+----------+--------------+
| | 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.
Antwoord 2, Autoriteit 22%
Ik denk dat ik je zal beginnen met de tijd complexiteit van een gelinkte lijst:
Indexeren—->O(n)
Aan het einde invoegen / verwijderen —->O(1) of O(n)
Midden invoegen / verwijderen —>O(1) met iterator O(n) met uit
De tijdscomplexiteit voor het invoegen aan het einde hangt af van of je de locatie van het laatste knooppunt hebt, als je dat doet, zou het O(1) zijn, anders moet je door de gekoppelde lijst zoeken en de tijdscomplexiteit zou spring naar O(n).
Antwoord 3, autoriteit 5%
Rood-zwarte bomen:
- Invoegen – O(log n)
- Ophalen – O(log n)
- Verwijderen – O(log n)
Antwoord 4, autoriteit 5%
Houd er rekening mee dat, tenzij u uw eigen gegevensstructuur schrijft (bijv. gekoppelde lijst in C), dit sterk kan afhangen van de implementatie van gegevensstructuren in uw taal/framework naar keuze. Bekijk als voorbeeld de benchmarks van Apple’s CFArray bij Ridiculous Fish. In dit geval verandert het gegevenstype, een CFArray uit het CoreFoundation-framework van Apple, de gegevensstructuren, afhankelijk van het aantal objecten dat zich daadwerkelijk in de array bevindt – van lineaire tijd naar constante tijd bij ongeveer 30.000 objecten.
Dit is eigenlijk een van de mooie dingen van objectgeoriënteerd programmeren – je hoeft niet te weten hoehet werkt, alleen dathet werkt, en de ‘ hoe het werkt’ kan veranderen afhankelijk van de vereisten.
Antwoord 5, autoriteit 4%
Niets zo nuttig als dit: Algemene gegevensstructuurbewerkingen:
Antwoord 6
Big-O afgeschreven voor hashtabellen:
- Invoegen – O(1)
- Ophalen – O(1)
- Verwijderen – O(1)
Houd er rekening mee dat er een constante factor is voor het hashing-algoritme, en de afschrijving betekent dat de werkelijke gemeten prestaties dramatisch kunnen variëren.