Nell’attesa di avere il tempo di scrivere le soluzioni per l’ultima edizione della gara ABC, propongo a chi è interessato (alcuni di voi sono davvero bravi!) le seguenti domande da risolversi in ordine.
Data la soluzione naïve di abc_checksum che implementa pedissequamente quanto descritto nel testo:
Si determini il caso peggiore.
Si fornisca una stima della complessità computazionale di tale soluzione (in notazione \mathcal{O}).
Si provi che tale stima non può essere migliorata, ovvero che il bound trovato è stretto.
Il tempo di calcolo dell’MCD, con la relativa complessità computazione, è trascurabile.
La soluzione naive sarebbe mantenersi una lista dei checksum precedenti (che sia un vector o altro non ci importa più di tanto) e per ogni nuovo pacchetto controllare che sia coprimo con tutti i precedenti.
Direi che il caso peggiore lo abbiamo quando il pacchetto corrente è valido, visto che dobbiamo scorrere tutta la lista dei pacchetti precedenti senza trovare un errore.
La complessità della soluzione naive nel caso peggiore è T\cdot\sum_{i = 1}^{N}{(i - 1)} = T \cdot \frac{N(N - 1)}{2}, dove T è la complessità dell’MCD. Considerando T \approx \mathcal{O}(1) la complessità diventa \mathcal{O}(N^2).
Per fare un’analisi della complessità nel caso medio partirei dalla probabilità p che due numeri siano coprimi tra loro. (Occhio che qui mi sto avventurando nell’ignoto, potrei scrivere stupidaggini enormi senza accorgermene). Sappiamo che p = \frac{1}{\zeta(2)} = \frac{6}{\pi^2}. Se consideriamo la lista L dei checksum precedenti, la probabilità che il pacchetto corrente C sia coprimo con i primi k è p^k.
La lunghezza media della sequenza di pacchetti coprimi a C dovrebbe essere quindi la media pesata in base alle probabilità di ogni lunghezza possibile, \frac{\sum_{i=1}^{N}{i \cdot p^i}}{\sum_{i=1}^{N}{p^i}}
Forse basta dire che nel caso peggiore la soluzione naive esegue \frac{N\cdot(N - 1)}{2} operazioni e quindi in quel caso la complessità è \mathcal{O}(N^2)?
Sì, davo per scontato che quella fosse chiara (qui un esempio).
D’accordo, ma non cattura completamente il caso peggiore. Sicuramente tutti i checksum devono essere validi, ma come devono essere affinché siano tutti validi?
Anche nel caso in cui i fattori che compongono tutti i vari checksum sono numeri primi diversi , senza che di fatto ogni numero sia primo no?
Voglio dire , esempio stupido: 2 5 21 tutti i checksum sono validi senza che effettivamente i numeri risultino tutti primi.
So che non cambia molto era giusto per verifcare se ho capito bene in quanto la mia soluzione non da 100/100
Il fatto è che (se non ho fatto male i conti) i primi tra 2 e 4e6 sono circa 2,7e5, quindi al massimo puoi trovare solo 2,7e5 numeri coprimi tra loro tra 2 e 4e6 e questi sono tutti primi
Intendi stretto solamente per quanto riguarda il caso pessimo, giusto?
Perché in generale (considerando anche il caso ottimo) direi che l’algoritmo naive ha un lower bound Ω(N).
Comunque se ho capito bene la domanda, ci basta dimostrare che nel caso pessimo abbiamo almeno Ω(N^2) operazioni. La formula è sempre quella già riportata da @dp_1 e siccome upper/lower bound coincidono abbiamo quindi un bound stretto (tight) e possiamo affermare quindi che l’algoritmo nel caso pessimo ha una complessità di Θ(N^2).
Sì, tutto questo topic riguarda esclusivamente il caso peggiore.
Quanto scritto da @dp_1 è una sovrastima della complessità computazionale. Sicuramente è vero che l’algoritmo nel caso peggiore è \mathcal{O}(P^2), ma si può fare di meglio basandosi sul punto 1, che è stato risolto.
In effetti, è abbastanza facile convincersi che dato un checksum c non è possibile che tutti i checksum da 1 a c-1 siano validi e quindi da controllare. (È vero nella soluzione proposta si scorre comunque tutto il vettore, ma ai fini di questa analisi consideriamo valide solo le posizioni per cui dobbiamo effettivamente fare qualcosa, ovvero calcolare l’MCD).
In realtà la colpa è un po’ mia, nel non aver definito sin dall’inizio cosa intendessi esattamente.
È vero che nella soluzione proposta dato c scorro tutte le posizioni nel vettore da 1 a c-1, ma è altrettanto vero che solo in un numero limitato di queste posizioni faccio veramente qualcosa (ovvero li confronto effettivamente andandone a calcolare l’MCD).
Provo a riformulare la richiesta: nel caso peggiore, complessivamente, quante chiamate a gcd() vengono effettuate?
Nel caso peggiore dovrei farle tutte no?
Se abbiamo stabilito come caso peggiore il caso in cui tutti i checksum siano validi io non ne posso escludere dal controllo, potrei evitare di richiamare la funzione su quelli non validi, ma nel caso peggiore la devo richiamare per ogni c o mi sto perdendo qualcosa?
Penso di aver capito, il numero di chiamate a gcd() per ogni checksum è limitato al numero di fattori primi x tali che x ≤ M (ovvero pi(M)), quindi inserendo in una lista i checksum validi la complessità - del caso pessimo supponendo gcd() in O(1) - dovrebbe diventare O(P⋅pi(M))
Se la sequenza di primi è ordinata - e se non mi sto sbagliando - ne controlliamo al più 0+1+2+3+...+pi(M)*(M-pi(M)), ma sono troppo pigro per sviluppare bene i calcoli
Questo lo possiamo fare solo nel caso in cui tutti i checksum siano primi però, se ad esempio inserisco prima 4 e solo dopo 2; o sbaglio?
