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

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
carmnu
Messaggi: 9
Iscritto il: 13 giu 2007, 10:33

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

Messaggio da 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.
Ultima modifica di carmnu il 16 giu 2007, 15:06, modificato 3 volte in totale.
Avatar utente
mitchan88
Messaggi: 469
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da mitchan88 »

Premesso che non so bene come si trova la complessità temporale di un algoritmo composto :oops:
Quicksortando e trovando la differenza minima di due consecutivi si dovrebbe trovare il risultato, anche se va oltre l'n logn :?
[url:197k8v9e]http://antrodimitch.wordpress.com[/url:197k8v9e]

Membro del fan club di Ippo_
CapitanoPo
Messaggi: 68
Iscritto il: 02 lug 2006, 11:08

Messaggio da 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 :D
Rispondi