[Teoria] Confronto fra i tempi di esecuzione

[Raider991]

Ciao ragazzi.Stavo cercando di fare un esercizio che in pratica mi da una tabella dove per ogni funzione $ f(n) $ e tempo $ t $ mi chiede di determinare la massima dimensione di $n$ di un problema che può essere risolto nel tempo $ t $.Ad esempio come prima funzione mi da $log(n)$ e mi chiede per quale valore massimo di $n$ un algoritmo con questa complessità può essere risolto in 1 secondo,1 minuto,1 ora?Potete aiutarmi facendomi capire come ragionare??Grazie in anticipo!!!

[el_brando]

Secondo me ti manca un dato del problema, cioè la velocità del processore.

Diaciamo sia \( s = \frac{istruzioni}{secondi} \) questa velocità. Per risolvere un problema di complessità \( \log n \) in un secondo, è necessario che \( n \) sia al massimo pari a \( 2^s \). Per risolverlo in un minuto, è necessario che \( n \) sia al massimo pari a \( 2^{s\cdot 60} \).

In generale, fissato un \( s \) (che dovrebbe essere un dato del problema), devi risolvere la seguente equazione: \( \frac {f(n)}{s} = t \) ricavando \( n \).

A titolo di esempio, se supponiamo che la velocità sia di una istruzione al secondo, cioè \( s = 1 \):
da \( \log n \) in un secondo (\( t = 1 \)) risulta \( n = 2 \);
da \( \log n \) in un minuto (\( t = 60 \)) risulta \( n = 2^{60} \).