Complexité temporelle de 2 ^ sqrt (n)

11

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?

Gaara
la source
3
Veuillez indiquer la raison du vote négatif sur la question. Merci!
Gaara
4
Honnêtement, je soupçonne que les gens confondent cela avec une question extrêmement triviale, mais il n'est pas immédiatement évident pour moi de le prouver de toute façon, alors je vais écrire une réponse et voir si cela change d'avis.
Ixrec
3
Temps sous-exponentiel, deuxième définition, selon un article de Wikipedia (Avertissement: je n'ai pas downvote; et je ne sais pas assez sur ce sujet pour dire si c'est correct ou non.)
rwong
1
Génial! Temps sous-exponentiel: "le temps d'exécution de certains algorithmes peut croître plus rapidement que n'importe quel polynôme, mais il est encore beaucoup plus petit qu'un exponentiel". Cela répond définitivement à ma question et élargit mes connaissances sur l'analyse Big O. Merci beaucoup
Gaara
1
C'est bien moins que O (2 ^ n), surtout pour les grands nombres. Prenons l'exemple d'une collection de 10 000 éléments. 2 ^ 10000 est un nombre avec environ 3000 chiffres, c'est le nombre de cycles qu'il faudrait pour effectuer une opération O (2 ^ n) dessus. Avec O (2 ^ sqrt (n)), vous êtes à un nombre à 30 chiffres. La différence est extrêmement énorme pour les grands nombres en faveur de la solution sqrt (pour 1 million d'éléments qui est (nombre avec 300 000 chiffres) * cycle cpu contre (nombre avec 300 chiffres) * cycle cpu).
Andy

Réponses:

16

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 : NR + et g : NR + , on a fO ( g ) si et seulement si lim sup n → ∞ f ( n ) / g ( n ) ∈ R .

Une fonction f : NR + a au plus une croissance polynomiale si et seulement s'il existe une constante kN telle que fO ( nn k ). Étudions cela pour kN 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.

5gon12eder
la source
6

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.

gnasher729
la source