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
grazie mille...ma studi informatica???
[mod="Fioravante Patrone"]MOD (Fioravante Patrone):
In attesa che Riuzaki trovi il tempo per inserire (se vuole) un avatar conforme al regolamento, ho cancellato quello che aveva inserito. [/mod]
In attesa che Riuzaki trovi il tempo per inserire (se vuole) un avatar conforme al regolamento, ho cancellato quello che aveva inserito. [/mod]
"Riuzaki":
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.....
Nessun reato: ci ho tenuto a specificare che è richiesta solo l'accortezza di scrivere quando si sa cosa si scrive, altrimenti lasciar rispondere altri, anche perché nessuno obbliga nessuno a scrivere $n$ post a settimana.
E siccome ho visto che 3 tuoi interventi su 3 avevano qualcosa che non andava, ci ho tenuto a precisare il concetto.
Si mi scuso con Sergio e Fioravante Patrone, ora l'ho modificata.
Scusate ma sono tornato ora dalle vacanze non ho avuto tempo di farlo prima
Scusate ma sono tornato ora dalle vacanze non ho avuto tempo di farlo prima
"Riuzaki":
grazie mille...ma studi informatica???
No, ho una laurea triennale in ingegneria del cinema e dei mezzi di comunicazione e sto finendo la specialistica di matematica.
Solo perchè questo esercizio lo presi dal "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein" segnalo la soluzione per via analitica del problema:
http://www.matematicamente.it/forum/2-n-100n-2-con-lambert-t101837.html
http://www.matematicamente.it/forum/2-n-100n-2-con-lambert-t101837.html
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo