MINIMUM A MAXIMUM SOUČASNĚ
PROBLÉM
Nalézt současně minimum i maximum zadaného číselného pole.
ALGORITMUS
Jednoduchý algoritmus MINANDMAX potřebuje k současnému nalezení minima i maxima asi 2*N porovnání.
IMPLEMENTACE
Jednotka: vnitřní funkce
Globální proměnné: číselné pole A.
Parametr: přirozené číslo N - počet prvlů v poli A.
Vrací: Hodnoty minima a maxima oddělené mezerou
MINANDMAX: procedure expose A.
parse arg N
Min = A.1; Max = A.1
do J = 2 to N
if A.J < Min then Min = A.J
else if A.J > Max then Max = A.J
end
return Min Max
|
Učebnice uvádějí, že efektivnější algoritmus má časovou složitost, vyjádřenou počtem porovnání, FORMAT(3*N/2-2,,0):
MINIMAX: procedure expose A.
parse arg J, N
if N = J then return A.J A.J
if N = J + 1
then if A.J < A.N
then return A.J A.N
else return A.N A.J
else do
parse value MINIMAX(J, J + 1) with Min1 Max1
parse value MINIMAX(J + 2, N) with Min2 Max2
return MIN(Min1, Min2) MAX(Max1, Max2)
end
|
Nejprve upozornění, první vyvolání funkce musí být příkazem (např.) say MINIMAX(1,N), tedy se dvěma parametry. Za druhé, implementační omezení na počet vnoření volání podprogramů znamená, že právě uvedenou funkci nemůžeme použít pro rozsáhlá pole. Proto uvádím následující nerekurzívní verzi s FORMAT(3*N/2,,0) porovnáními:
NON_RECURSIVE_MINIMAX: procedure expose A.
parse arg N
push 1 N; Min = A.1; Max = A.1
do while QUEUED() > 0
pull J R
select
when R = J
then do
Min = MIN(A.J, Min)
Max = MAX(A.J, Max)
end
when R = J + 1
then do
if A.J < A.R
then do
Min = MIN(A.J, Min)
Max = MAX(A.R, Max)
end
else do
Min = MIN(A.R, Min)
Max = MAX(A.J, Max)
end
end
otherwise
push J (J + 1)
if J+2 <= R then push (J + 2) R
end
end
return Min Max
|
Pro N=50000 funkce MINANDMAX(N) potřebuje 99993 porovnání, zatímco NON_RECURSIVE_MINIMAX(N) jen 75000. Jenže funkce MINANDMAX splní svůj úkol za 4.34 sekund - a funkce NON_RECURSIVE_MINIMAX? Za 43.33 sekund ...
SOUVISLOSTI
Literatura Baudoin C., Meyer B. Méthodes de programmation Edition Eyrolles 61, Bd Saint-Germain Paris 1978
|
