[Algoritmi] Ordinare delle funzioni in base alla notazione O
Date le seguenti funzioni
$2n log^3n , 4 root(3)(n log n), log n^4, n^log n, n^2 log n^3, n^n , n^5, (log n)^n, 10 root(4)n , $
$n log root(3)n , 7 log^3 n , n^3 root(3) n , 10 log log^2 n , 3 log n^4, n!, n^(1/log n)$
ordinarle scrivendole da sinistra a destra in modo tale che la funzione f (n) venga posta a
sinistra della funzione g(n) se f (n) = O(g(n)).
Allora io le ho ordinate come segue, l'unica cosa non ho inserito $n^(1/log n)$ perché non so se considerarla una sublineare visto l'esponente con frazione oppure se considerarla polinomiale...sapreste indicarmi come posso considerarla e soprattutto l'ordine di queste funzioni è corretto?
$10 log log^2 n , log n^4, 3 log n^4, 7 log^3 n , 4 root(3)(n log n) , 10 root(4)n , n log root(3)n , 2n log^3n ,$
$n^2 log n^3 , n^3 root(3) n , n^log n , n^5, (log n)^n , n!, n^n$
$2n log^3n , 4 root(3)(n log n), log n^4, n^log n, n^2 log n^3, n^n , n^5, (log n)^n, 10 root(4)n , $
$n log root(3)n , 7 log^3 n , n^3 root(3) n , 10 log log^2 n , 3 log n^4, n!, n^(1/log n)$
ordinarle scrivendole da sinistra a destra in modo tale che la funzione f (n) venga posta a
sinistra della funzione g(n) se f (n) = O(g(n)).
Allora io le ho ordinate come segue, l'unica cosa non ho inserito $n^(1/log n)$ perché non so se considerarla una sublineare visto l'esponente con frazione oppure se considerarla polinomiale...sapreste indicarmi come posso considerarla e soprattutto l'ordine di queste funzioni è corretto?
$10 log log^2 n , log n^4, 3 log n^4, 7 log^3 n , 4 root(3)(n log n) , 10 root(4)n , n log root(3)n , 2n log^3n ,$
$n^2 log n^3 , n^3 root(3) n , n^log n , n^5, (log n)^n , n!, n^n$
Risposte
non ho controllato se l'ordine è giusto, ma la funzione su cui dici di avere dei dubbi è in realtà costante, essendo
$n^(1/(log n))=2^((log n)/(log n))=2$
$n^(1/(log n))=2^((log n)/(log n))=2$
Ciao e grazie.
Quindi se è costante va posta come prima. Io per ordinarle mi sono basato su una tabella che ci ha fornito il prof ovvero questa:
$O(1) , O(log log n) , O(log n) , O( root(c) n) con (c > 1) , O(n) , O(n log n)$
$O(n^2 ) , O(n^3 ) , O(n^k ) con (k ≥ 1) , O(a^n ) con (a > 1) , O(n!)$
Quindi se è costante va posta come prima. Io per ordinarle mi sono basato su una tabella che ci ha fornito il prof ovvero questa:
$O(1) , O(log log n) , O(log n) , O( root(c) n) con (c > 1) , O(n) , O(n log n)$
$O(n^2 ) , O(n^3 ) , O(n^k ) con (k ≥ 1) , O(a^n ) con (a > 1) , O(n!)$
prego! Ho anche controllato il resto e mi pare ci siano 2 coppie di funzioni con l'ordine da invertire, una è $n^5,n^(log n)$, l'altra prova a cercarla tu 
Ok per $n^5$. Però l'altra coppia non riesco a trovarla. Per me ora sono tutte giuste. Inizialmente avevo il dubbio con $n^n$. Poi sul libro ho letto che è possibile dimostrare che $ n! = o(n^n)$ e quindi l'ho messa per ultima. Mentre le altre funzioni mi sono basato sulla tabella che ti ho scritto su e non mi sembra che vi siano errori. Ci penso un altro po....grazie ancora!!
Niente io l'altra coppia non la trovo...
ah scusa non volevo farti ammattire è che mi ero proprio dimenticato di rispondere 
comunque apprezzo molto il fatto che almeno tu ci abbia provato, purtroppo spesso vediamo più facilmente gli errori degli altri che non i nostri!
L'altra coppia che dicevo io è $4(n\log n)^(1/3)$,$10n^(1/4)$
comunque apprezzo molto il fatto che almeno tu ci abbia provato, purtroppo spesso vediamo più facilmente gli errori degli altri che non i nostri!
L'altra coppia che dicevo io è $4(n\log n)^(1/3)$,$10n^(1/4)$
Non ti devi preoccupare assolutamente, anzi grazie per la tua disponibilità. Purtroppo, io non riesco a vedere i miei errori, perché quando sbaglio, sbaglio per convinzione!!Ho ordinato in quel modo la coppia, perché non ho ragionato con l'esponente frazionario, ma (perdonami la baggianata che sto per dire) ho ragionato come per i log che quelli con l'esponente più grande andavano più a destra delle alte.
Comunque grazie ancora. Riusciresti a consigliarmi un libro dove si capisce bene la notazione asintotica e tutti argomenti correlati, io ho il libro di Cormen (Introduzione agli algoritmi e alle strutture dati) ma vorrei qualcosa di meglio...
Comunque grazie ancora. Riusciresti a consigliarmi un libro dove si capisce bene la notazione asintotica e tutti argomenti correlati, io ho il libro di Cormen (Introduzione agli algoritmi e alle strutture dati) ma vorrei qualcosa di meglio...
"Skeggia":
Riusciresti a consigliarmi un libro dove si capisce bene la notazione asintotica e tutti argomenti correlati, io ho il libro di Cormen (Introduzione agli algoritmi e alle strutture dati) ma vorrei qualcosa di meglio...
Algoritmi e strutture dati - 2°ed di Alan A. Bertossi, A. Montresor - CittàStudi
completo come il cormen, discorsivo ma formalmente molto accurato, ha parecchi esercizi con tutte le soluzioni (quelle senza soluzione sono sul sito dell'autore). Io lo ho utilizzato come testo principale, il Cormen come compendio ed approfondimento
altro materiale:
- sezione dispense: post479901.html#p479901
- sezione algoritmica: syllabus-per-scienze-informatiche-t80143.html
Ciao grazie. Sei stato gentilissimo!
"Skeggia":
Ciao e grazie.
Quindi se è costante va posta come prima. Io per ordinarle mi sono basato su una tabella che ci ha fornito il prof ovvero questa:
$O(1) , O(log log n) , O(log n) , O( root(c) n) con (c > 1) , O(n) , O(n log n)$
$O(n^2 ) , O(n^3 ) , O(n^k ) con (k ≥ 1) , O(a^n ) con (a > 1) , O(n!)$
E quando ho combinazioni di una con un altra? Come mi comporto?
Ho provato a fare questo esercizio, con i seguenti numeri da ordinare:
Li ho ordinati così:
E' giusto? Solo $f_5 (n)$ non ho capito dove collocarlo...
Osserva prima di tutto che \(n^{1/3} = 2^{(\log_2 n)/3} \geq 2^{\sqrt{\log_2 n}}\) per \(n\) sufficientemente grande. A questo punto devi semplicemente confrontare questa funzione con quella del logaritmo. L'idea migliore è a mio parere quella di fare il logaritmo in base due di entrambi. A questo punto devi confrontare \(\log_2 \log_2 n\) con \( \sqrt{\log_2 n}\) e credo che a questo punto sia immediato concludere che ..
EDIT: Corretto disuguaglianza.. Ma se la disuguaglianza fosse stata quella che avevo scritto non avrebbe avuto senso fare il confronto anche con una successione ancora più bassa. Ti consiglio di leggere le risposte con più attenzione, usando un approccio più critico. Tutti possiamo sbagliare. Questo era un refuso, ma può capitare di fare errori più seri.
EDIT: Corretto disuguaglianza.. Ma se la disuguaglianza fosse stata quella che avevo scritto non avrebbe avuto senso fare il confronto anche con una successione ancora più bassa. Ti consiglio di leggere le risposte con più attenzione, usando un approccio più critico. Tutti possiamo sbagliare. Questo era un refuso, ma può capitare di fare errori più seri.
"apatriarca":
Osserva prima di tutto che \(n^{1/3} = 2^{(\log_2 n)/3} \leq 2^{\sqrt{\log_2 n}}\) per \(n\) sufficientemente grande. A questo punto devi semplicemente confrontare questa funzione con quella del logaritmo. L'idea migliore è a mio parere quella di fare il logaritmo in base due di entrambi. A questo punto devi confrontare \(\log_2 \log_2 n\) con \( \sqrt{\log_2 n}\) e credo che a questo punto sia immediato concludere che ..
Partendo dalla tua trasformazione posso dire che $n = 2^(\log_2 n)$? Se si, magari mi torna utile in altri esercizi...
Però non ho capito come ti escono quei due numeri facendo il log di entrambi.
Io l'ho fatto ed ottengo $\log_2 2^{(\log_2 n)/ 3}$ e $\log_2 2^{\sqrt(\log_2 n)}$ che diventano rispettivamente $(\log_2 n)/3 \log_2 2$ e $\sqrt(\log_2 n) \log_2 2$, sbaglio qualcosa?
In questo caso il primo mi sembra più piccolo...
Quindi l'ordine finale diventa $f_4 f_2 f_5 f_1 f_3$
Per definizione se \(\log_2 n = x\) allora \( 2^x = 2^{\log_2 n} = n. \) Non è solo una proprietà.. È proprio una definizione. Inoltre siccome \( \log_2 n^\alpha = \alpha\,\log_2 n \) si ha anche che \( n^\alpha = 2^{\alpha\,\log_2 n}. \)
Dopodiché facendo il logaritmo di \( \log_2 n \) si ottiene \( \log_2 ( \log_2 n ), \) mentre facendo quello di \( 2^\sqrt{\log_2 n}\) si ottiene \( \log_2 2^\sqrt{\log_2 n} = \sqrt{\log_2 n} \, \log_2 2 = \sqrt{\log_2 n}. \) Da dove viene il \(3\) nei tuoi risultati?
EDIT: Ma se abbiamo detto che \(f_5\) è minore di \(n^{1/3}\), l'ordine non è certamente quello..
EDIT2: Ho notato che avevo scritto la disuguaglianza al contrario e ho corretto. Si ha ovviamente che \( (\log_2 n)/3 \geq \sqrt{\log_2 n}\) per \(n\) sufficientemente grande e siccome l'esponenziale è strettamente monotona crescente allora questa relazione si trasferisce anche alle funzioni che stavamo prendendo in considerazione. Nota che posso confrontare i logaritmi nell'altro confronto per la stessa ragione. Fare un logaritmo preserva le disuguaglianze..
Dopodiché facendo il logaritmo di \( \log_2 n \) si ottiene \( \log_2 ( \log_2 n ), \) mentre facendo quello di \( 2^\sqrt{\log_2 n}\) si ottiene \( \log_2 2^\sqrt{\log_2 n} = \sqrt{\log_2 n} \, \log_2 2 = \sqrt{\log_2 n}. \) Da dove viene il \(3\) nei tuoi risultati?
EDIT: Ma se abbiamo detto che \(f_5\) è minore di \(n^{1/3}\), l'ordine non è certamente quello..
EDIT2: Ho notato che avevo scritto la disuguaglianza al contrario e ho corretto. Si ha ovviamente che \( (\log_2 n)/3 \geq \sqrt{\log_2 n}\) per \(n\) sufficientemente grande e siccome l'esponenziale è strettamente monotona crescente allora questa relazione si trasferisce anche alle funzioni che stavamo prendendo in considerazione. Nota che posso confrontare i logaritmi nell'altro confronto per la stessa ragione. Fare un logaritmo preserva le disuguaglianze..
Abbiamo detto di fare il logaritmo dei numeri dati, che sono $2^{(\log_2 n)/3}$ e $2^{\sqrt{\log_2 n}\)$
Perché fai il logaritmo di $\log_2 n$ e $2^\sqrt(\log_2 n)$?
Perché fai il logaritmo di $\log_2 n$ e $2^\sqrt(\log_2 n)$?
Ok, allora non ci eravamo capiti. Per confrontare \(f_2\) ed \(f_5\) non è necessario fare altro che portare \(f_2\) in forma esponenziale come ti ho mostrato. A questo punto quando hai esponenziali con la stessa base puoi confrontare gli esponenti. \(f_2\) ha certamente un esponente che è maggiore di \(f_5\) quando \(n\) è sufficientemente grande e quindi \(f_5 \leq f_2\). A questo punto c'è una sola funzione che è minore di \(f_2\) e con cui ha senso confrontare \(f_5\). Così come sono scritte non è facile confrontarle per cui ho deciso di calcolarne il logaritmo. Facendo il logaritmo trovo due funzioni che hanno \(log_2 n\) come argomento e quindi posso confrontarle dicendo che il logaritmo è minore della radice quadrata quando \(log_2 n\) e quindi \(n\) è sufficientemente grande. Per cui l'ordine è \(f_4, f_5, f_2, f_1, f_3\).
Grazie apatriarca per la tua disponibilità.
Un ultima cosa, sto facendo altri esercizi partendo dalla tabella postata da Skeggia... però quando ho una notazione combinazione di una con un altra come mi comporto? Ad esempio un logaritmo di una radice o una radice di un logaritmo o ancora, un numero elevato una radice o un logaritmo ecc ecc... come faccio a capire l'ordine di precedenza?
Un ultima cosa, sto facendo altri esercizi partendo dalla tabella postata da Skeggia... però quando ho una notazione combinazione di una con un altra come mi comporto? Ad esempio un logaritmo di una radice o una radice di un logaritmo o ancora, un numero elevato una radice o un logaritmo ecc ecc... come faccio a capire l'ordine di precedenza?
Imparati le proprietà dei logaritmi, degli esponenziali e in generale di tutte le funzioni con cui hai a che fare.. Il logaritmo di un radice è ad esempio il logaritmo moltiplicato per una costante. Un numero elevato ad un logaritmo si può sempre semplificare cambiando la base del logaritmo e così via..
Capisco, grazie mille!
Se ho ancora problemi mi faccio vivo di nuovo
Se ho ancora problemi mi faccio vivo di nuovo
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo