Trade-offs

Unir dos colecciones

Un programa recibe por la red muchos fragmentos de datos y los va uniendo en una sola secuencia. Unir dos listas es enlazar la cola de una con la cabeza de la otra.

Un programa une muchas secuencias de n y m elementos, una tras otra, y casi nunca las recorre. ¿Cuánto cuesta unir dos de ellas en cada representación?Las dos O(1): unir es solo apuntar al principio de la segunda secuencia sin mover nadaListas con cabeza y cola: O(1). Arrays: O(m) para copiar la segunda, y O(n + m) si creceLas dos O(n + m): unir obliga a recorrer las dos secuencias para saber dónde acabanListas: O(m), recorriendo la segunda para enlazarla. Arrays: O(1), porque basta ampliar el rango