PDF de programación - Determinación del k-ésimo mayor de n números

Determinación del k-ésimo mayor de n números

Algoritmos

Facultad de Informática
Universidad de A Coruña

Algoritmos

Determinaci ón del k-ésimo mayor de n n úmeros

Determinación del k-ésimo mayor de n números (i)

Primera solución : O(n2).

Ordenar decrecientemente los n números. O(n2)
O(1)
Devolver k-ésimo.

1.
2.
función KésimoMayor ( V[1..n], k ): número { 1 ≤ k ≤ n }

Ordenar por inserción ( V[1..n] ); { decrecientemente }
devolver V[k]

fin función

Algoritmos

Determinaci ón del k-ésimo mayor de n n úmeros

Determinación del k-ésimo mayor de n números (ii)

Segunda solución : O(k 2 + (n− k)k). Si k = n
1. Ordenar decrecientemente los k 1os números.
2. Para cada número en (k . . . n],
3.
función KésimoMayor ( V[1..n], k ): número { 1 ≤ k ≤ n }

O(k 2)
O((n− k)k)

2 entonces O(n2).

insertar si procede.

O(k)

Ordenar por inserción ( V[1..k] ); { decrecientemente }
para i := k+1 hasta n hacer

j := k;
si V[j] < V[i] entonces

mientras j > 1 y V[j-1] < V[i] hacer

V[j] := V[j-1]; j := j - 1;

fin mientras
V[j] := V[i]

fin para
devolver V[k]

fin función

Algoritmos

Determinaci ón del k-ésimo mayor de n n úmeros

Determinación del k-ésimo mayor de n números (iii)

Tercera solución : O(n + k log n). Si k = n

2 entonces O(n log n).

1. Crear un montículo de máximos con los n nos
2. Realizar k − 1 eliminaciones
3. Obtener el mayor

O(n)
O(k(log n))
O(1)

función KésimoMayor ( V[1..n], k ): número { 1 ≤ k ≤ n }

Crear Montículo Máximos ( V[1..n], M );
para i := 1 hasta k-1 hacer

EliminarMax ( M );

fin para
devolver ObtenerMayor ( M );

fin función

Algoritmos

Determinaci ón del k-ésimo mayor de n n úmeros

Determinación del k-ésimo mayor de n números (iv)

Cuarta solución : O(k + (n− k) log k). Si k = n
2 entonces O(n log n).
1. Crear montículo de mínimos con los k primeros nos O(k)
O((n− k) log k)
2. Para cada número en (k . . . n],
3.
4.
5.
función KésimoMayor ( V[1..n], k ): número { 1 ≤ k ≤ n }

Determinar si insertar en montículo O(1)

Eliminar mínimo
Insertar nuevo número

O(log k)
O(log k)

Crear Montículo Mínimos ( V[1..k], M );
para i := k+1 hasta n hacer

si ObtenerMenor ( M ) < V[i] entonces

EliminarMin ( M );
Insertar ( V[i], M )

fin para
devolver ObtenerMenor ( M );

fin función

Algoritmos

Determinaci ón del k-ésimo mayor de n n úmeros