Tengo una duda respecto al TAD Tabla, cuando piden por ejemplo la funcion:
// Asocia a d el valor s en t; si ya tenía un valor asociado, lo redefine
void insertarT(int d, string s, Tabla &t);
En este caso piden O(1) tiempo ejecucion en el caso promedio, queria saber si estaria bien primero acceder a la lista correspondiente para ese d, osea en la posicion d % n de la tabla acceder a la lista y buscar el elemento del dominio d, si esta, modificarle el codominio correspondiente, y sino, agregar un nuevo nodo a la lista con la correspondencia d-s pasada como parametros en la función solicitada. ¿Eso cumpliria O(1) tiempo promedio?
En respuesta a Gianfranco Servidio Diaz
Re: [Parcial][Julio][2016][Ejercicio 3]
de Fernando Fernandez -
Sí, esa es la idea. Es O(1) porque se supone que cada lista tiene pocos elementos. Es promedio porque en algunos casos podría no ocurrir.
Si, en cambio, se supiera que no existe una asociación para la clave que se quiere insertar, entonces la operación podría hacerse en O(1) peor caso porque alcanza con insertar al principio de la lista.
En respuesta a Fernando Fernandez