Complexité temporelle de 2 ^ sqrt (n)

Je suis en train de résoudre une question d'algorithme et mon analyse est qu'elle fonctionnerait sur O (2 ^ sqrt (n)). Quelle est sa taille? Est-ce que cela équivaut à O (2 ^ n)? Est-ce encore du temps non polynomial?

C'est une question intéressante. Heureusement, une fois que vous savez comment le résoudre, ce n'est pas particulièrement difficile.

Pour les fonctions f : N → R ⁺ et g : N → R ⁺ , on a f ∈ O ( g ) si et seulement si lim sup _{n → ∞} f ( n ) / g ( n ) ∈ R .

Une fonction f : N → R ⁺ a au plus une croissance polynomiale si et seulement s'il existe une constante k ∈ N telle que f ∈ O ( n ↦ n ^k ). Étudions cela pour k ∈ N arbitraire mais fixe .

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 première égalité est vraie parce que les deux, le nominateur et le dénominateur, sont des fonctions stables à croissance monotone. La deuxième égalité utilise l'identité x ^y = e ^{log ( x ) y} . La limite n'est pas finie car l'exposant dans l'expression finale n'est pas borné ci-dessus. Sans donner de preuve formelle, on peut supposer que n ^1/2 domine log ( n ) asymptotiquement. Par conséquent, la fonction en question dépasse la croissance polynomiale.

Cependant, sa croissance est strictement inférieure à exponentielle, où exponentielle est définie (par moi, à cet effet) comme O ( n ↦ 2 ^{c n} ) pour c > 0. Le montrer est encore plus simple.

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

pour tout c > 0 fixe . Par conséquent, la complexité de la fonction se situe vraiment entre le polynôme et l'exponentielle.

Quelle est sa taille? Eh bien, O (2 ^ sqrt (n)) est exactement de la taille :-(

Pour avoir une idée de ce que cela signifie, imaginez que votre algorithme ne serait pas seulement O (2 ^ sqrt (n)), mais qu'il prend en fait précisément 2 ^ sqrt (n) nanosecondes sur votre ordinateur:

n = 100: 2 ^ 10 = 1024 nanosecondes. Pas de temps du tout. n = 1000: 2 ^ 31.xxx = 2 milliards de nanosecondes. Deux secondes, c'est perceptible. n = 10 000: 2 ^ 100 ≈ 10 ^ 30 nanosecondes = 10 ^ 21 secondes = 30 trillions d'années.

C'est beaucoup mieux que 2 ^ n nanosecondes, où n = 100 prendrait 30 billions d'années, mais la taille des problèmes que vous pouvez résoudre est encore assez limitée. Si vous considérez un problème "résoluble" si votre ordinateur peut le résoudre en une semaine, cela représente environ 6 x 10 ^ 14 nanosecondes, soit environ n = 2 400. D'un autre côté, jusqu'à n = 400 peut être résolu en une milliseconde.

(En pratique, pour n = 10 000, O (2 ^ sqrt (n)) et O (2 ^ n) prennent exactement le même temps: trop de temps pour l'attendre.)

Il dépasse tout polynôme. Prenez un autre algorithme prenant n ^ 1000 secondes. Ce qui est pratiquement insoluble pour n = 2. Cet algorithme prend plus de temps jusqu'à ce que n soit d'environ 885 millions. Mais vraiment, qui s'en soucie? À ce stade, le nombre d'années que prennent les deux algorithmes est un nombre de 9 000 chiffres.