La complessità del tempo di 2 ^ sqrt (n)

Questa è una domanda interessante. Fortunatamente, una volta che sai come risolverlo, non è particolarmente difficile.

Per le funzioni f : N → R ^{& plus;} e g : N → R ^{& plus;} , abbiamo f ∈ O ( g ) se e solo se lim sup _{n → ∞} f ( n ) / g ( n ) ∈ R .

Una funzione f : N → R ^{& plus;} ha al massimo una crescita polinomiale se e solo se esiste una costante k ∈ N tale che f ∈ O ( n & mapsto; n ^k ). Risolviamolo per arbitrario ma corretto k ∈ N .

lim sup _{n → ∞} 2 ^{( n 1/2 )} / n ^k = lim _{n → ∞} 2 ^{( n 1/2 )} / n ^k = lim _{n → ∞} e ^{log (2) n 1/2} / e ^{log ( n ) k} =
lim _{n → ∞} e ^{log (2) n 1/2 - log ( n ) k} = ∞ ∉ R

La prima uguaglianza è vera perché entrambi, il nominatore e il denominatore, sono funzioni stabili monotonicamente crescenti. La seconda uguaglianza usa l'identità x ^y = e ^{log ( x ) y} . Il limite non è finito perché l'esponente nell'espressione finale non è limitato sopra. Senza dare una dimostrazione formale, si può presumere che n ^1/2 domini il log ( n ) asintoticamente. Pertanto, la funzione in questione supera la crescita polinomiale.

Tuttavia, la sua crescita è strettamente inferiore all'esponenziale, dove è definito esponenziale (da me, per questo scopo) come O ( n & mapsto; 2 ^{c n} ) per c > 0. Mostrare questo è ancora più semplice.

lim sup _{n → ∞} 2 ^{c n} / 2 ^{( n 1/2 )} = lim _{n → ∞} 2 ^{c n - n 1/2} = ∞ ∉ R

per ogni fisso c > 0. Pertanto, la complessità della funzione è da qualche parte tra polinomiale ed esponenziale.

Quanto è grande? Bene, O (2 ^ sqrt (n)) è esattamente quanto è grande: - (

Per avere un'idea di cosa significa, immagina che il tuo algoritmo non sarà solo O (2 ^ sqrt (n)), ma che in realtà richiede esattamente 2 ^ sqrt (n) nanosecondi sul tuo computer:

n = 100: 2 ^ 10 = 1024 nanosecondi. Nessun tempo. n = 1000: 2 ^ 31.xxx = 2 miliardi di nanosecondi. Due secondi, è evidente. n = 10.000: 2 ^ 100 ≈ 10 ^ 30 nanosecondi = 10 ^ 21 secondi = 30 trilioni di anni.

Questo è un lotto migliore di 2 ^ n nanosecondi, dove n = 100 richiederebbe 30 trilioni di anni, ma la dimensione dei problemi che è possibile risolvere è piuttosto limitata. Se consideri un problema "risolvibile" se il tuo computer può risolverlo in una settimana, si tratta di 6 x 10 ^ 14 nanosecondi, ovvero n = 2400. D'altra parte, fino a n = 400 può essere risolto in un millisecondo.

(In pratica, per n = 10.000 sia O (2 ^ sqrt (n)) che O (2 ^ n) prendono esattamente lo stesso tempo: troppo tempo per aspettare.)

Supera qualsiasi polinomio. Prendi un altro algoritmo prendendo n ^ 1000 secondi. Che è praticamente irrisolvibile per n = 2. Questo algoritmo richiede più tempo fino a quando n è circa 885 milioni. Ma davvero, a chi importa? A quel punto il numero di anni che entrambi gli algoritmi assumono è un numero di 9.000 cifre.