Forelæsning 7/10 2003: Noget om hvorfor det er godt at kende til algoritmer og store O også selvom de fleste er skrevet i forvejen

Indgår i forelæsning her.

Hvorfor kan vi ikke nøjes med ArrayList, den har da alle de metoder vi ska' bru'e?

add(...) er stort set O(1) - OK.
iterator fungerer uden for meget overhead.

Men:
add(...) er en gang imellem O(n) !!!!
contains(...), indexOf(...) er O(n) og ganget med konstant fra "equals"

Overvej: Hvis vi har en ArrayList (længde n) af ArrayLists (hver af gnst. lgd. m), hvad mon indexOf(...) koster??

Andre Collections så som HashSet og diverse SortedSets har bedre karakteristika.


Sidst rettet 6. oktober 2003, Henning Christiansen