Hola a todos tengo una consulta teórica, alguien me podría explicar cual es la complejidad de inserción, búsqueda y eliminación de
elementos en un arreglo ordenado, saludos.
30/06/2010, 20:30
| ||||
| ||||
 Consulta Teórica Hola a todos tengo una consulta teórica, alguien me podría explicar cual es la complejidad de inserción, búsqueda y eliminación de elementos en un arreglo ordenado, saludos. |
|
30/06/2010, 22:54
| ||||
| ||||
| Respuesta: Consulta Teórica no , no va ligado a ningun tipo de algoritmo es mas generico por ejemplo la ida es ver como se puede aprovechar la gracia de que el arreglo este ordenado para reducir la complejidad de algunas operaciones por ejemplo en un arreglo ordenado se puede usar busqueda binaria entonces la complejidad se reduce de o(n) a o(log n) y en eliminar y agregar tambien. bueno esta es una de las tantas maneras que existen y la que tengo clara. |
|
01/07/2010, 00:56
| |||
| |||
| Respuesta: Consulta Teórica pues realmente la complejidad computacional de agregar, accesar y eliminar va a depender del algoritmo q estes utilizado. Tal y como tu dices la complejidad de insertar, eliminar y buscar se reduce en O(n log n) cuando tu utilizas un arbol binario. Los algoritmos que no mantienen una estructura de los elementos tales como de la burbuja, quicksort entre otros, sus busquedas en el peor de los casos sería O(n), Sin embargo si utilizas algun tipo de estructura tales como los arboles, o implementas algun algoritmo de busqueda basado en algun algorimo de inserccion. Pues la complejidad dependera de cual utilices |
| Etiquetas: Ninguno |
