[Algoritmi] Dimostrazione di complessità computazionale
Salve ragazzi, ho qualche difficoltà con questo semplice problema di complessità, spero qualcuno possa darmi una mano.
Devo dimostrare che \( f(n)= \lceil \log n \rceil \) è una funzione di complessità propria.
Per definizione, dobbiamo dimostrare che:
1- la funzione è monotona non decrescente (banale);
2- esiste una MdT con I/O \( M \) che dato come input una stringa \( x \) e ponendo \( n = |x| \), restituisca in output una stringa di lunghezza \( \lceil \log n \rceil \) in tempo \( O(n + \log n) \) ed in spazio \( O(\log n) \).
Ecco come ho impostato il problema:
\( M \) conta il numero di caratteri presenti nel nastro di input tramite un contatore binario che viene memorizzato nel nastro di lavoro. Poi \( M \) scrive sul nastro di output tanti semi-blank quanti sono i caratteri presenti nel nastro di lavoro. Quindi in output avremo effettivamente una stringa di \( \sqcap \) lunga \( \lceil \log n \rceil \).
Analisi dello spazio
Lo spazio consumato è dato solo dalla dimensione del nastro di lavoro per cui è \( O( \log n) \).
Analisi del tempo
Lettura dell'input: \( O( n ) \)
Scrittura dell'output: \( O( \log n) \)
Determinazione del nastro di lavoro: ??
Purtroppo non riesco a determinare una complessità inferiore a \( O( n \log n) \) per l'ultimo punto. Non so se ho calcolato male la complessità o se ho proprio sbagliato l'approccio.
Qualche buon'anima riesce ad aiutarmi ? (Anche fornendo una soluzione totalmete diversa dalla mia volendo).
Grazie in anticipo...
Devo dimostrare che \( f(n)= \lceil \log n \rceil \) è una funzione di complessità propria.
Per definizione, dobbiamo dimostrare che:
1- la funzione è monotona non decrescente (banale);
2- esiste una MdT con I/O \( M \) che dato come input una stringa \( x \) e ponendo \( n = |x| \), restituisca in output una stringa di lunghezza \( \lceil \log n \rceil \) in tempo \( O(n + \log n) \) ed in spazio \( O(\log n) \).
Ecco come ho impostato il problema:
\( M \) conta il numero di caratteri presenti nel nastro di input tramite un contatore binario che viene memorizzato nel nastro di lavoro. Poi \( M \) scrive sul nastro di output tanti semi-blank quanti sono i caratteri presenti nel nastro di lavoro. Quindi in output avremo effettivamente una stringa di \( \sqcap \) lunga \( \lceil \log n \rceil \).
Analisi dello spazio
Lo spazio consumato è dato solo dalla dimensione del nastro di lavoro per cui è \( O( \log n) \).
Analisi del tempo
Lettura dell'input: \( O( n ) \)
Scrittura dell'output: \( O( \log n) \)
Determinazione del nastro di lavoro: ??
Purtroppo non riesco a determinare una complessità inferiore a \( O( n \log n) \) per l'ultimo punto. Non so se ho calcolato male la complessità o se ho proprio sbagliato l'approccio.
Qualche buon'anima riesce ad aiutarmi ? (Anche fornendo una soluzione totalmete diversa dalla mia volendo).
Grazie in anticipo...
Risposte
Anche io faccio complessità, se non sbaglio, dovresti evitare di contarle, ma scrivere direttamente il carattere semi-blank.
Quindi poi occuperai solo (log n) sul nastro 2 per il contatore i che tiene traccia del cursore
Quindi poi occuperai solo (log n) sul nastro 2 per il contatore i che tiene traccia del cursore
Grazie per la risposta ma non pernso si possa fare come dici tu.
Se scrivo direttamente in output i semi-blank avrò in output un numero \( n \) di caratteri (pari all'input), ma la definizione esplicita che dobbiamo avere \( \lceil \log n \rceil \) caratteri, per quello conto i caratteri. Comunque non è lo spazio che non riesco a "far tornare", è il tempo. Con la mia soluzione il nastro di lavoro occupa spazio \( O( \log n) \), e va bene. E' quanto tempo impiego per generare il nastro di lavoro che mi da noia. Io arrivo ad una complessità in tempo \( O(n\log n) \), ma è troppo alta...
Se scrivo direttamente in output i semi-blank avrò in output un numero \( n \) di caratteri (pari all'input), ma la definizione esplicita che dobbiamo avere \( \lceil \log n \rceil \) caratteri, per quello conto i caratteri. Comunque non è lo spazio che non riesco a "far tornare", è il tempo. Con la mia soluzione il nastro di lavoro occupa spazio \( O( \log n) \), e va bene. E' quanto tempo impiego per generare il nastro di lavoro che mi da noia. Io arrivo ad una complessità in tempo \( O(n\log n) \), ma è troppo alta...
Per definizione una MdT con I/O, non conta i nastri di input ed output per determinare la complessità.
Quindi tu puoi scrivere direttamente, usando dei contatori binari nei nasti, che occupano al max log n simboli
Quindi tu puoi scrivere direttamente, usando dei contatori binari nei nasti, che occupano al max log n simboli
Conosco la definizione di MdT con I/O, infatti nel calcolo della complessità in spazio ho tenuto conto solo del nastro di lavoro:
E comunque con la tua soluzione abbiamo sul nastro di output un numero lineare di caratteri e non logaritmico, come richiede la dimostrazione.
Ripeto, il mio problema è la complessità in tempo. In particolare la determinazione della complessità del nastro di lavoro (quelli di input ed output vanno bene).
Analisi dello spazio
Lo spazio consumato è dato solo dalla dimensione del nastro di lavoro per cui è \( O(\log n) \).
E comunque con la tua soluzione abbiamo sul nastro di output un numero lineare di caratteri e non logaritmico, come richiede la dimostrazione.
Ripeto, il mio problema è la complessità in tempo. In particolare la determinazione della complessità del nastro di lavoro (quelli di input ed output vanno bene).
Guarda che essendo numeri in binario, dei fare il logaritmo. Quindi se usi un contatore da 1 a n, hai un nastro log n.
Ti serve solo un contatore per stampare in output i semi-blank
Ti serve solo un contatore per stampare in output i semi-blank
Ma scusa, hai letto la soluzione al mio primo post ? Certo che mi basta un contatore binario sul nastro di lavoro, ma è appunto determinare la complessità in tempo di ciò che non mi torna...
Ho risolto, mi sono accorto di una piccola svista nel fare i calcoli (la distrazione !). Alla fine ho raggiunto \( O( (\log n)^2) \) per determinare il nastro di lavoro. Quindi ricapitolando...
Analisi del tempo
Lettura dell'input: \( O(n) \)
Scrittura dell'output: \( O(\log n) \)
Determinazione del nastro di lavoro: \( O( (\log n)^2) \)
Complessità totale: \( O(n) \)
Come richiede la definizione. Ora la dimostrazione dovrebbe essere corretta !
Analisi del tempo
Lettura dell'input: \( O(n) \)
Scrittura dell'output: \( O(\log n) \)
Determinazione del nastro di lavoro: \( O( (\log n)^2) \)
Complessità totale: \( O(n) \)
Come richiede la definizione. Ora la dimostrazione dovrebbe essere corretta !
Hai ragione, ho letto male.
Però log n quadro non p logaritmico..
COmunque per la definizione hai anche O(n) per leggere l'input oltre alla O(f(n))
Però log n quadro non p logaritmico..
COmunque per la definizione hai anche O(n) per leggere l'input oltre alla O(f(n))
Giusto, è polilogaritmico. Ma l'importante è, come hai sottolineato anche tu, che non superi il lineare (per quanto rigarda il tempo).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo