Exponentielles doubles vs exponentielles simples

8

Voici quatre principes que je ne peux pas concilier:

Je sens qu'il me manque une subtilité concernant la définition d'un algorithme à temps exponentiel comme fonctionnant en plutôt qu'en , mais je ne le suis pas sûr précisément où se trouve la subtilité.O(2poly(n))O(2n)

badroit
la source
1
J'ai édité les balises et les tuiles car, vraiment, cette question n'a rien à voir avec la théorie de la complexité: elle concerne la notation mathématique et le comportement asymptotique des fonctions mathématiques.
David Richerby

Réponses:

25

Le problème se résume à une terminologie ambiguë.

(ab)c=abc , mais . En d'autres termes, les exposants ne sont pas associatifs.a(bc)abc

Classiquement, les exponentielles imbriquées sans parenthèses sont regroupées de cette deuxième manière, car c'est plus utile. Donc . Si nous voulions parler de , nous pourrions simplement écrire place, nous réservons donc la double notation exponentielle pour l'autre cas.22n=2(2n)22n(22)n22n

Draconis
la source
3
Cette convention est la seule raisonnable. Comme vous l'avez décrit, choisir l'autre façon de grouper serait inutile car nous pourrions déjà exprimer cette valeur / fonction en utilisant au lieu d'un "double exponentiel" fantaisiste. abc
Bakuriu
1
@Bakuriu Oh, en effet, bien qu'il soit important de noter que ce n'est qu'une convention. (Il pourrait aussi y avoir la convention de toujours utiliser des parenthèses, c'est ce que fait LaTeX: il refuse de deviner comment se regrouper a^b^cet lance une erreur à la place.)
Draconis
1
Toute notation est "juste une convention". Décrire « » comme «juste une convention» suggère qu'il existe d'autres alternatives plausibles mais, vraiment, il n'y en a pas. abc=a(bc)
David Richerby
1
@DavidRicherby Certes, toute notation est conventionnelle! Mais cela ne signifie pas que cela ne vaut pas la peine d'être noté. C'est un choix délibéré des mathématiciens d'utiliser cette notation: et c'est un bon choix, car il élimine l'ambiguïté et est plus utile que l'alternative. Mais c'est toujours un choix, et rien ne vous empêche de le définir différemment (en plus de confondre les lecteurs sans réel gain).
Draconis
2
@Bakuriu Je n'irais pas jusqu'à dire que c'est la seule convention sensée, car il me semble très sensé de supposer que toutes les opérations sont évaluées de gauche à droite, sauf s'il y a des parenthèses. C'est ce que nous faisons avec l'addition et la soustraction et ce que les enfants apprennent à l'école primaire avec "PEMDAS". Le fait que l'exponentiation ne respecte pas la convention m'a fait trébucher dans le passé, et à peu près tous ceux qui en ont entendu parler pour la première fois.
6005
16

a(bc) n'est pas identique à . Lorsque les gens écrivent , ils signifient généralement , pas .(ab)c22k2(2k)(22)k

DW
la source