Divisori in sottoinsieme di [2n]
Divisori in sottoinsieme di [2n]
Dato un insieme di n+1 interi compresi tra 1 e 2n dare un algoritmo il più efficiente possibile che individua (se presente...) una coppia di suoi elementi che siano uno un divisore dell'altro.
Non capisco... come è possibile farlo in tempo linerare?
Se, in un caso speciale, i numeri fossero dati nell'intervallo [n+1,2n], il programma diventa equivalente a trovare, dati degli interi $ ~ a_1,a_2,\ldots,a_n $, i 2 che sono uguali (sapendo che ce ne sono).
Ma questo forse è un po' più chiaro che è difficile farlo in tempo lineare!
Se, in un caso speciale, i numeri fossero dati nell'intervallo [n+1,2n], il programma diventa equivalente a trovare, dati degli interi $ ~ a_1,a_2,\ldots,a_n $, i 2 che sono uguali (sapendo che ce ne sono).
Ma questo forse è un po' più chiaro che è difficile farlo in tempo lineare!
Perchè ???edriv ha scritto: Se, in un caso speciale, i numeri fossero dati nell'intervallo [n+1,2n], il programma diventa equivalente a trovare, dati degli interi $ ~ a_1,a_2,\ldots,a_n $, i 2 che sono uguali (sapendo che ce ne sono).
Ma questo forse è un po' più chiaro che è difficile farlo in tempo lineare!
Puoi farlo in tempo lineare usando un array ausiliario di dimensione n che usi per ricordarti degli elementi che hai già visto. E' la soluzione ovvia di questo sottoproblema, prende tempo e spazio lineare (a dirla tutta l'array ausiliario può essere eliminato, ma questa è un'altra storia). La soluzione del problema originale non è molto più difficile, su.
La vostra discussione mi ha fatto venire in mente questa soluzione: si crea un array $ app $ di $ 2 n $celle, si scorre l'array in input e si valorizza $ [tex] $app = 1[/tex] se $ i $ è un elemento dell'input. Se si trova un elemento presente 2 volte ci si ferma (perchè si è trovata la coppia cercata), altrimenti si esegue il seguente programma:
per ogni $ ind $ che va da 1 a $ n: $
se $ app[ind] = 1 $, si controlla se nell'array $ app $ c'è qualche altro elemento del tipo $ k * ind $ (con $ k $ naturale maggiore di 1) tale che $ app[k * ind] = 1 $. Se questo elemento esiste, si è trovata la coppia cercata (cioè $ (ind, k * ind)) $ e si termina, altrimenti
$ next $ $ ind $
Questo programma compie al più $ n + \sum_{i = 1}^{n} \frac{n}{i} $ passi, cioè $ n + n * \sum_{i = 1}^{n} \frac{1}{i} $, che è all'incirca $ n + n * \log n $.
Il programma è quindi O(nlogn). Forse, ma non ho idea di come si possa fare a dimostrarlo, il programma è anche O(n), perchè se gli elementi dell'insieme sono pochi, la parte "dispendiosa" del programma viene eseguita poco, mentre se gli elementi sono molti, la probabilità di terminare in fretta aumenta. Magari, nel caso particolare di $ n + 1 $ elementi c'è una dimostrazione più semplice.
Mah...
per ogni $ ind $ che va da 1 a $ n: $
se $ app[ind] = 1 $, si controlla se nell'array $ app $ c'è qualche altro elemento del tipo $ k * ind $ (con $ k $ naturale maggiore di 1) tale che $ app[k * ind] = 1 $. Se questo elemento esiste, si è trovata la coppia cercata (cioè $ (ind, k * ind)) $ e si termina, altrimenti
$ next $ $ ind $
Questo programma compie al più $ n + \sum_{i = 1}^{n} \frac{n}{i} $ passi, cioè $ n + n * \sum_{i = 1}^{n} \frac{1}{i} $, che è all'incirca $ n + n * \log n $.
Il programma è quindi O(nlogn). Forse, ma non ho idea di come si possa fare a dimostrarlo, il programma è anche O(n), perchè se gli elementi dell'insieme sono pochi, la parte "dispendiosa" del programma viene eseguita poco, mentre se gli elementi sono molti, la probabilità di terminare in fretta aumenta. Magari, nel caso particolare di $ n + 1 $ elementi c'è una dimostrazione più semplice.
Mah...
Ok, questa è la soluzione che usa la forza bruta. Corretta, ma fa del lavoro inutile e per questo non è lineare in tempo. Infatti se gli interi sono n+1 ci si può limitare a tentare solo dei particolari valori di k (con riferimento al messaggio di Ipparco), quali?
(Hint: la coppia di numeri esiste sempre, per quale motivo?)
(Hint: la coppia di numeri esiste sempre, per quale motivo?)
Basta considerare l'applicazione che manda $ x = 2^u v $, con $ v $ dispari, in $ v $. In altre parole la funzione che restituisce l'intero diviso per la masima potenza del due che lo divide. Due interi che hanno la stessa immagine sono uno un divisore dell'altro. Poichè il risultato dell'applicazione è un dispari questa funzione mappa l'insieme [2n] in n distinti interi, tutti i dispari minori di 2n. Dunque se scegliamo n+1 interi in [2n] almeno due di essi avranno la stessa immagine (principio della piccionaia) quindi saranno uno un divisore dell'altro. Questa osservazione suggerisce una variante dell'algoritmo forza-bruta postato da Ipparco che consiste nel tentare solo i valori di k che sono potenze di 2. Se lo analizzate vi rendete conto che lavora in tempo lineare.