Confronto fra i tempi di esecuzione

lordb
Ciao a tutti mi rendo conto che questi siano problemi molto semplici per voi, ma io sono totalmente un novizio nel campo matematica-informatica ...
Ecco non credo di aver capito cosa mi chiede questo esercizio, ho provato a risolverlo per le 2 $ f(n) $ più semplici come vedrete rispetto a $ t=1 s $
Non voglio che mi risolviate tutto l'esercizio , ma ho bisogno di capire come si opera in questo caso:

Risposte
Rggb1
Dal testo: un dato algoritmo esegue un problema di dimensione n in f(n) microsecondi
Per esempio se la funzione è il logaritmo, un problema di dimensione 10 impiega log(10) microsecondi; se ho a disposizione 1 secondo, la dimensione massima del problema sarà n tale che log(n)=1000000 ovvero un milione [che vale..? calcola te]
Dove sta la difficoltà?

PS. Non ho capito invece che calcoli hai scritto sotto... come è possibile che un problema di dimensione $10^8$, che ha tempo di esecuzione $n=f(n)$ ovvero $10^8$ microsecondi ovvero 100 secondi, sia risolvibile in un solo secondo? ;)

lordb
ah grazie mille ecco cosa sbagliavo
io invece credevo che le $ f(n) $ di sinistra non fossero riferite solo all'algoritmo ( che poi non so perchè moltiplicavo per $ 10^-6 $ ), ma anche al valore del problema al numeratore ....
Grazie ancora sono un nabbo stratosferico :-D

edit: quindi per f(n)n :

1 secondo >>>> $n= 10^6$
1 minuto >>>> $n= 6*10^7$
1 ora >>>>>>> $n= 36*10^8$
1 giorno >>>>> $n= 24*36*10^8$

e così via o non ho capito ancora niente ? :shock:

quindi per 1 secondo:
$n= f(n) >> n= 10^6
$n^2= f(n)>> n= 10^3
$2^n=f(n)>> n= 19,9
$n! =f(n) >>n=9,4 $

è giusto ?
ora il problema è quello con $lg n$ che sta per $log_2 n$ , devo cambiare base visto che la calcolatrice esegue solo$ log_10 $?

inoltre tu quando hai fatto l'esempio di un problema $n=10$ che ci mette $logn$ microsecondi , non dovrebbe essere $log10 = 1$ microsecondo ? ($log_10 10 = 1 )

Rggb1
edit: quindi per f(n)n :

1 secondo >>>> $n= 10^6$
1 minuto >>>> $n= 6*10^7$
1 ora >>>>>>> $n= 36*10^8$
1 giorno >>>>> $n= 24*36*10^8$

e così via o non ho capito ancora niente ? :shock:

Giusto.

quindi per 1 secondo:
$n= f(n) >> n= 10^6
$n^2= f(n)>> n= 10^3
$2^n=f(n)>> n= 19,9
$n! =f(n) >>n=9,4 $

è giusto ?

Giusto (anche se, visto si cerca la massima dimensione, io toglierei i decimali; ma è una finezza).

ora il problema è quello con $lg n$ che sta per $log_2 n$ , devo cambiare base visto che la calcolatrice esegue solo$ log_10 $?

Sicuro sia il logaritmo in base due invece del logaritmo naturale?
Comunque, usa meno la calcolatrice e più la testa, puoi calcolare tutto con le funzioni inverse (ti ricorda qualcosa?)

inoltre tu quando hai fatto l'esempio di un problema $n=10$ che ci mette $logn$ microsecondi , non dovrebbe essere $log10 = 1$ microsecondo ? ($log_10 10 = 1 )

Non ho messo calcoli, se noti bene. Ho scritto solo "se il problema ha dimensione 10 l'algoritmo impiega log(10) microsecondi", senza calcolare log(10).

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.