Costos Assimptòtics TADs

Aquesta és la recopilació dels costos dels TAD usats a EI:

AVL:
ÚTIL PER A …
– Nombre gran i indeterminat (gestió dinàmica de l’espai)
– Recorregut ordenat per clau. Accés per clau (accés logarítmic per l’accés a les claus)

COSTOS…
Inserció: O(log n)
Consulta: O(log n)
Generar Iterador: O(1)
Recórrer Taula:O(N)
Eliminar Dada:O(Log N)

TAULA DISPERSIÓ:
ÚTIL PER A …
– Nombre mitjanament gran i sense moltes variacions (estructura acotada però poc desaprofitament per poques variacions)
– Accés directe per clau (temps constant)
– No són necesaris recorreguts per clau

COSTOS…
Inserció: O(1)
Consulta: O(1)
Eliminar Dada:O(1)

LLISTA ACOTADA:
ÚTIL PER A …
– Nombre petit d’elements (poc desaprofitament de l’espai)
– Útil per a recórrer segons l’ordre d’inserció.
– Si s’ha de cercar per clau i la mida es petita, el cost és acceptable

COSTOS…
Inserció al final : O(1)
Consulta:
Ordenada —- O(log n)
Desordenada —O(n)
Generar Iterador: O(1)
Eliminar Dada:O(N)

CUA AMB PRIORITAT:
ÚTIL PER A …
– Correcte quan l’ordre es realitza en funció a un factor diferent a l’ordre d’inserció.
– No es pot recórrer. Per a recórrer-la fa falta anar desfent una còpia de la mateixa.

COSTOS…
encuar: O(log n)
Desencuar: O(log n)
Consulta la primera: O(1)

Anuncis
Aquesta entrada ha esta publicada en Informàtica - Desenvolupament. Afegeix a les adreces d'interès l'enllaç permanent.

Deixa un comentari

Fill in your details below or click an icon to log in:

WordPress.com Logo

Esteu comentant fent servir el compte WordPress.com. Log Out /  Canvia )

Google photo

Esteu comentant fent servir el compte Google. Log Out /  Canvia )

Twitter picture

Esteu comentant fent servir el compte Twitter. Log Out /  Canvia )

Facebook photo

Esteu comentant fent servir el compte Facebook. Log Out /  Canvia )

S'està connectant a %s