Výpocet maxima, PA 2
podme ušetrit nejakú pamät: nech N = 2M
Program Maximum3
assign ? ||j: 0 ? j < N:: A[j] = max(A[2j], A[2j+1])?
A[0] = maximum, v case O(log N)
pouzijeme pomocnú premennú t
- na zaciatku t = N
- v kazdom kroku jej hodnota bude t := ?t/2?
nech A0[j] sú pociatocné hodnoty v A[j]
invariant:
?max j: 0 ? j < t:: A[j]? = ?max j: 0 ? j < N:: A0[j]?
raz urcite t = 1 a potom A[0] = ?max j: 0 ? j < N:: A0[j]?