Algoritmos y Estructuras de Datos (VJ1215)

Aquí aplicamos los resultados obtenidos en el ejercicio 5 del tema 2 y en el ejercicio 2.a del tema 4.

Sea n la talla del vector.

• Tanto con un vector no ordenado como con con una lista enlazada no ordenada: el primer bucle tiene coste temporal O(n); el segundo bucle tiene coste temporal O(n²); por tanto, el coste temporal del algoritmo es O(n + n²) = O(n²).

• Tanto con un vector ordenado como con una lista enlazada ordenada: el primer bucle tiene coste temporal O(n²); el segundo bucle tiene coste temporal O(n); por tanto, el coste temporal del algoritmo es O(n² + n) = O(n²).

• Con un arbol binario de búsqueda: el primer bucle tiene coste temporal O(n²); el segundo bucle tiene coste temporal O(n²); por tanto, el coste temporal del algoritmo es O(n² + n²) = O(n²).

• Tanto con un montículo binario como con un árbol AVL: el primer bucle tiene coste temporal O(n log n); el segundo bucle tiene coste temporal O(n log n); por tanto, el coste temporal del algoritmo es O(n log n + n log n) = O(n log n).