🚀 go-pugleaf

Rudy Gevaert <rudy@zeus.rug.ac.be> wrote:
> Heeft er iemand een overzicht van de standaard datastructuren, met de tijdsanalyse van de basis bewerkingen?

Probleem is dat niet alleen de datastructuur op zich belangrijk is, maar
ook de implementatie van bepaalde operatoren op die datastructuur.

Bv. een copy-on-write implementatie van een array heeft O(1) copy
operatie maar een O(n) write-element complexiteit. Een 'gewone'
implementatie heeft O(n) complexiteit voor copieren en O(1) om een
element te vervangen. 

(PS dit is niet zomaar een academische mogelijkheid, de implementaties
van std::string in C++, wat je als een fancy array kan bekijken,
waren vroeger meestal copy on write, maar om verschillende redenen
stapt men nu meestal over naar copy-on-copy. (threading is er eentje
van)

> Bv stack, toevoegen en verwijderen kan in constante tijd

Enkel bij een fixed size stack. Een algemenere implementatie moet
bijvoorbeeld rekening houden met het resizen van de stack
(O(n) meestal)

> Of een link, ik heb al eens op google gezocht, maar niets gevonden (zal aan de sleutelwoorden liggen waarschijnlijk, "datastructure time").

Ga eens te rade bij een medestudent die informatica studeert. Normaliter
zal die wel een cursus hebben over tijdscomplexiteits-analyse. Samen
met je gezond verstand zou je dat al een eind op weg moeten helpen.

cu bart

-- 
http://www.irule.be/bvh/