Algoritmos de Ordenamiento y Grafos: Eficiencia y Aplicaciones
Clasificado en Diseño e Ingeniería
Escrito el en español con un tamaño de 9,05 KB
Algoritmos de Ordenamiento
QuickSort
QuickSort tiene una complejidad en el peor caso de O(n2), que ocurre cuando el pivote elegido resulta ser el elemento más pequeño o más grande del subconjunto. La ecuación de recurrencia es T(n-1) + n + c.
Pseudocódigo:
Si (#S = 0 o #S1 = 1) res <- S Sino pivote <- S[1] Para cada Valor de S[2...inf] Si Valor < pivote S1 <- S1 + Valor Sino S2 <- S2 + Valor res <- QuickSort(S1) + pivote + QuickSort(S2)
MergeSort
MergeSort tiene una complejidad de O(n log n). La ecuación de recurrencia es 2T(n/2) + n + c.
Pseudocódigo Merge (O(n)):
S3 <- [] I <- 1 J <- 1 Para k <- 1 hasta (#S1 + #S2) Si S1aux[i] < S2aux[j]... Continuar leyendo "Algoritmos de Ordenamiento y Grafos: Eficiencia y Aplicaciones" »