Si consideri un insieme S di n >= 2 distinti numeri interi.
•Si descriva ed analizzi un algoritmo che dato in input S, determini x,y appartenenti ad S tali che |x – y| >= |w – z| per tutti w, z appartenenti ad S. L’algoritmo deve avere una complessità di tempo O(n).
•Si descriva ed analizzi un algoritmo che dato in input S, determini x,y appartenenti ad S tali che |x – y| <= |w – z| per tutti w, z appartenenti ad S. L’algoritmo deve avere una complessità di tempo O(n log n).
Per il primo punto penso che questa sia una buona soluzione:
Codice: Seleziona tutto
punto1(S)
if S[1] < s[2] then
min <- S[1]
max <- S[2]
else
min <- S[2]
max <- S[1]
for i=3 to length[S]
if S[i] < min
min <S> max
max <- S[i]
x <- max
y <- min
Grazie.