3.3.5. El problema de selección.

• Utilizando el procedimiento Pivote podemos resolverlo en O(n).

Selección (T: array [1..n]; s: integer)

var i, j, l: integer;

begin

i:= 1; j:= n;

repeat

Pivote (i, j, l);

if s < l then

j:= l-1

else if s > l then

i:= l+1;

until l=s;

return T[l];

end;

• El procedimiento es no recursivo. Además es una reducción: el problema es descompuesto en un solo subproblema de tamaño menor.

• En el mejor caso, el subproblema es de tamaño n/2:

t(n) = t(n/2) + a·n; t(n) ? O(n)

• En el peor caso (array ordenado) el subproblema es de tamaño n-1:

t(n) = t(n-1) + a·n; t(n) ? O(n2)

Diapositiva anterior

Ir a la primera diapositiva

Ver versión gráfica