Comparaciones de Algoritmos

 

Comparación Algoritmo de Búsqueda.

 

Concepto	Breve descripción	Característica principal	Recursiva-Iterativa	Nivel de eficiencia	Complejidad
Búsqueda secuencial	Busca un elemento comparándolo consecutivamente con cada uno de los elementos existente en el arreglo, hasta encontrar el elemento buscado o hasta llegar al final del arreglo.	Se utiliza cuando el vector no está ordenado o cuando no se puede ordenar.	Iterativo	2	Mejor caso: O(1) Peor caso: O(n) Caso medio: O(n)
Hashing	Caja negra que tiene como entrada una llave y como salida una dirección.	– consiste en convertir el elemento almacenado en una dirección dentro del array.	Iterativo	4	O(n)
Binaria	Divide y compara con elementos central; si el elemento es menor, se encuentra a la izquierda,  si el  elemento es mayor, se encuentra a la derecha.	Debe estar ordenado.	Recursivo	3	O(log2n)
Búsqueda en texto	Utiliza heurísticas (trata de métodos exploratorios durante la resolución de problemas).	– Evita comparaciones ya realizadas. – Mejora el algoritmo de fuerza bruta. – Busca cadenas de cualquier longitud por lo que se puede utilizar para frases extensas.	terativo.	3	O(n)
Hashing  Función Cuadrática	Eleva al cuadrado la clave y toma los dígitos centrales como dirección.	El número de dígitos a tomar queda determinado por el rango del índice.	Iterativo.	4
4: Mayor, 1: Menor

 

Comparación Algoritmo de Ordenamiento.

 

Concepto	Breve descripción	Característica principal	Recursivo-Iterativos	Nivel de eficiencia	Complejidad
Quicksort	Utiliza un pivote y ordena los elementos según él.	División por pivote.	Recursivo	1	O(n log n)
Bidireccional	Mejora el método de burbuja con menos comparaciones.	Va ordenando al mismo tiempo los dos extremos del vector.	Iterativo	4	O(n^2)
Shellsort	Asigna una distancia y ordena entre ellos.	Compara e intercambia.	Iterativo	3	O(n^1.25)
Heapsort	Almacena los elementos en un montículo y luego extrae el nodo que queda como raíz, La cima siempre contiene el menor elemento.	Utiliza un árbol binario para estructurar el proceso de ordenamiento.	Iterativo	2	O(n log n)
Inserción	Toma uno por uno los elementos y avanza hacia su posición con respecto a los anteriormente ordenados hasta recorrer todo el arreglo.	Se puede llegar a demorar mucho.	iterativo	5	O(n^2)