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
Nalezení K-tého nejmenšího prvku
     Find
     Modifind
     Select
Technika: Odstranění rekurze

Literatura
Baudoin C., Meyer B. Méthodes de programmation
Edition Eyrolles 61, Bd Saint-Germain Paris 1978


Obálka Obsah Index Hlavní stránka

změněno 8. srpna 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.