Aiuto su un problema facile su algoritmi
Ciao a tutti
Per voi di sicuro sarà molto facile ma io non riesco a capire come risorverlo....
es:
Qual è il più piccolo valore di $ n $ per cui un algoritmo il cui tempo di esecuzione è $ 100n^2 $ viene eseguito più velocemente di un algoritmo il cui tempo di esecuzione è $ 2^n $ sulla stessa macchina ?
Ecco non capisco cosa intentende con "tempo di esecuzione": il tempo di esecuzione finale ( quindi dovrei risoverlo in maniera algebrica $ n= 0 $ ----> $ 0 < 1 $ ma non credo abbia molto senso ciò) o intende il numero di istruzioni necessarie per il calcolo ( e quindi non saprei comunque come risolverlo poichè si fa riferimento a sempre uno stesso algoritmo ).
Se sapete come risolverlo fate riferimento a insertion sort o a merge sort (sono gli unici due che conosco per ora
)
Per voi di sicuro sarà molto facile ma io non riesco a capire come risorverlo....
es:
Qual è il più piccolo valore di $ n $ per cui un algoritmo il cui tempo di esecuzione è $ 100n^2 $ viene eseguito più velocemente di un algoritmo il cui tempo di esecuzione è $ 2^n $ sulla stessa macchina ?
Ecco non capisco cosa intentende con "tempo di esecuzione": il tempo di esecuzione finale ( quindi dovrei risoverlo in maniera algebrica $ n= 0 $ ----> $ 0 < 1 $ ma non credo abbia molto senso ciò) o intende il numero di istruzioni necessarie per il calcolo ( e quindi non saprei comunque come risolverlo poichè si fa riferimento a sempre uno stesso algoritmo ).
Se sapete come risolverlo fate riferimento a insertion sort o a merge sort (sono gli unici due che conosco per ora
)
Risposte
Ti stai facendo più problemi del dovuto. Devi infatti semplicemente risolvere la disequazione $100n^2 < 2^n$. Con tempo di esecuzione si intende il tempo necessario a completare l'esecuzione, ma questo era solo un esercizio sulla complessità.
a una disequazione esponenziale ....
come faccio a portarla alla forma elementare $A^x>B $ o $A^x 100n^2 $ non riesco ad andare avanti con quel $ n^2 $
come faccio a portarla alla forma elementare $A^x>B $ o $A^x
Non c'è un modo semplice per risolvere quella disequazione. Ti direi di risolverla in modo numerico. Devi in ogni caso provare solo i numeri naturali, e già con $n=20$ (ho provato un numero a caso...) la disequazione è vera.
Detto in maniera poco rigorosa, osservi che [tex]$2^{n}$[/tex]cresce molto più velocemente di [tex]$100n^2$[/tex].
Per numeri piccoli la diseguaglianza non è vera, ma andando avanti [tex]$2^{n}$[/tex] "sorpassa" [tex]$100n^2$[/tex]e da quel momento in poi la disequazione sarà sempre vera.
Per vedere quando avviene questo sorpasso, fai qualche prova.
Per[tex]$n=10$[/tex] ancora non è vera.
Per [tex]$n=15$[/tex] verifichi che è vera, quindi provando i numeri intermedi iniziando da [tex]$14$[/tex] risolvi il tutto.
Sono calcoli che ancora puoi fare senza calcolatrice in un tempo non esagerato. Magari rispolverando la moltiplicazioni in colonna.
Per numeri piccoli la diseguaglianza non è vera, ma andando avanti [tex]$2^{n}$[/tex] "sorpassa" [tex]$100n^2$[/tex]e da quel momento in poi la disequazione sarà sempre vera.
Per vedere quando avviene questo sorpasso, fai qualche prova.
Per[tex]$n=10$[/tex] ancora non è vera.
Per [tex]$n=15$[/tex] verifichi che è vera, quindi provando i numeri intermedi iniziando da [tex]$14$[/tex] risolvi il tutto.
Sono calcoli che ancora puoi fare senza calcolatrice in un tempo non esagerato. Magari rispolverando la moltiplicazioni in colonna.
@lordb: Per favore, trova un avatar più piccolo! (Cfr. regolamento, 2.3)
[asvg]axes(); // visualizza gli assi
stroke="red"; // seleziona il colore rosso
plot("100*x^2"); // disegna
stroke="green"; // seleziona il colore verde
plot("2^x"); // disegna[/asvg]
stroke="red"; // seleziona il colore rosso
plot("100*x^2"); // disegna
stroke="green"; // seleziona il colore verde
plot("2^x"); // disegna[/asvg]
Grazie a tutti ragazzi
@Gugo82 Perchè il mio avatar non va bene ? Tanto viene ridimensionato automaticamente ogni volta che carichi la pagina,quindi risulta della stessa grandezza dei vostri ...
@Gugo82 Perchè il mio avatar non va bene ? Tanto viene ridimensionato automaticamente ogni volta che carichi la pagina,quindi risulta della stessa grandezza dei vostri ...
cmq non è vero che non si può risolvere analiticamente ecco come si fa:
${2^n > 100*n^2} = {(2 ^ n) / 100 > n ^ 2}$
dato che $2 ^ n$ si può scrivere come $e ^ log(2 ^ n) = e ^ (n*log(2))$
allora procediamo come segue:
$1/100 > (n^2)/ (n*log(2)) = n < (log(2))/100$
${2^n > 100*n^2} = {(2 ^ n) / 100 > n ^ 2}$
dato che $2 ^ n$ si può scrivere come $e ^ log(2 ^ n) = e ^ (n*log(2))$
allora procediamo come segue:
$1/100 > (n^2)/ (n*log(2)) = n < (log(2))/100$
Non sono molto convinto dei passaggi:
$2^n > 100*n^2$
$(2^n)/(100) > n^2$
a questo punto hai sostituito $2^n = e^{n*log(2)}$
$(e^{n*log(2)})/(100) > n^2$
Ma a questo punto non mi è per niente chiaro come hai ottenuto l'ultima disequazione. Verrebbe invece
$1/100 > (n^2)/(e^{n*log(2)})$
che non si può semplificare semplicemente eliminando l'esponenziale.
Non ho idea se sia possibile risolvere analiticamente questa disequazione. Forse sì, non ci ho provato, ma credo sia infinitamente più facile fare qualche calcolo e ottenere la risposta in modo numerico.
$2^n > 100*n^2$
$(2^n)/(100) > n^2$
a questo punto hai sostituito $2^n = e^{n*log(2)}$
$(e^{n*log(2)})/(100) > n^2$
Ma a questo punto non mi è per niente chiaro come hai ottenuto l'ultima disequazione. Verrebbe invece
$1/100 > (n^2)/(e^{n*log(2)})$
che non si può semplificare semplicemente eliminando l'esponenziale.
Non ho idea se sia possibile risolvere analiticamente questa disequazione. Forse sì, non ci ho provato, ma credo sia infinitamente più facile fare qualche calcolo e ottenere la risposta in modo numerico.
si hai perfettamente ragione...in quel punto ho sbagliato....
Lordb, ha ragione Sergio. Spesso l'immagine non viene ridimensionata, quindi ti rinnovo l'invito di Gugo82.
Potresti ridimensionare tu stesso l'immagine e poi caricarla, oppure vedere se ne trovi una versione minore, oppure cambiare.
Vedi un attimo.
A Riuzaki: vedo che sei da poco arrivato, e che in questa sezione hai dato 3 suggerimenti in breve tempo in 3 topic diversi, suggerimenti poi rivelatisi errati o poco appropriati.
Ti chiederei quindi una maggiore attenzione: chi si rivolge al forum ha fiducia nelle risposte e diritto di ottenerne di idonee.
L'errore ogni tanto può ovviamente starci, ma se magari si è in dubbio meglio non scrivere nulla piuttosto che "tentare".
Ciao.
Potresti ridimensionare tu stesso l'immagine e poi caricarla, oppure vedere se ne trovi una versione minore, oppure cambiare.
Vedi un attimo.
A Riuzaki: vedo che sei da poco arrivato, e che in questa sezione hai dato 3 suggerimenti in breve tempo in 3 topic diversi, suggerimenti poi rivelatisi errati o poco appropriati.
Ti chiederei quindi una maggiore attenzione: chi si rivolge al forum ha fiducia nelle risposte e diritto di ottenerne di idonee.
L'errore ogni tanto può ovviamente starci, ma se magari si è in dubbio meglio non scrivere nulla piuttosto che "tentare".
Ciao.
[mod="Fioravante Patrone"]In atetsa che lordb trovi il tempo per inserire (se vuole) un avatar conforme al regolamento, ho cancellato quello che aveva inserito.[/mod]
io mi sono iscritto solo quest'anno all'università e ancora ho da imparare direi tutto....
ma non pensavo che dire qualcosa che si pensa anche se sbagliando fosse un reato scusa.....
ma non pensavo che dire qualcosa che si pensa anche se sbagliando fosse un reato scusa.....
comunque dato che sono testardo forse ora ci sono davvero :
$2^n > 100*n^2 = 100 > ((2^n)/(n^2)) = 100 > (log2(2^n))/(n^2) = 100 > (n*log2(2))/(n^2) = 100 > (log2(2))/n = n < (log2(2))/100$
spero di aver detto qualcosa di giusto questa volta
:$2^n > 100*n^2 = 100 > ((2^n)/(n^2)) = 100 > (log2(2^n))/(n^2) = 100 > (n*log2(2))/(n^2) = 100 > (log2(2))/n = n < (log2(2))/100$
spero di aver detto qualcosa di giusto questa volta
"Riuzaki":
io mi sono iscritto solo quest'anno all'università e ancora ho da imparare direi tutto....
[mod="Fioravante Patrone"]Parli con me?
Se sì, non posso fare altro che ribadire quanto ti è stato detto più volte: questo forum ha un regolamento.[/mod]
no con steven parlavo comunque non è niente di grave...
"Riuzaki":Ok, scusa per il malinteso.
no con steven parlavo comunque non è niente di grave...
"Riuzaki":
comunque dato che sono testardo forse ora ci sono davvero
$2^n > 100*n^2 = 100 > ((2^n)/(n^2)) = 100 > (log2(2^n))/(n^2) = 100 > (n*log2(2))/(n^2) = 100 > (log2(2))/n = n < (log2(2))/100$
spero di aver detto qualcosa di giusto questa volta
No, hai di nuovo commesso un errore. $(2^n)/(n^2) \ne (\log_2(2^n))/(n^2) = (1)/(n)$. Continui a commettere lo stesso errore, solo mascherato in modo diverso. Non si può togliere un esponenziale o aggiungere un logaritmo a piacimento.
Il problema nel "provare" a dare risposte senza sapere bene cosa si stia facendo è che si rischia di confondere ulteriormente chi cerca aiuto nel forum. Un errore può starci ma in questi primi post hai praticamente sempre dato risposte sbagliate. Ti consiglio quindi di controllare più approfonditamente le risposte che dai in cerca di errori.
ok daccordo mi sto zitto senti ma come si mette la base nelle formule dei logaritmi che non ci riesco??
senti ma come si mette la base nelle formule dei logaritmi che non ci riesco??
Devi scrivere semplicemente "log_2(x)".
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo