|x – y| <= |w – z|

[carmnu]

Ciao gente, ho un altro piccolo quesito da proporvi

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

Il punto 2 però non ne ho proprio idea di come si possa risolvere.
Grazie.

[mitchan88]

Premesso che non so bene come si trova la complessità temporale di un algoritmo composto
Quicksortando e trovando la differenza minima di due consecutivi si dovrebbe trovare il risultato, anche se va oltre l'n logn

[CapitanoPo]

sicuro che la complessità aumenti? perchè se lo ordini in nlogn e poi fai un ciclo in più credo che la complessità non vari (la notazione O() nasconde molte costanti).
Però non sono bravo in questi conti perciò potrei aver detto una grossa vaccata