Voici quatre principes que je ne peux pas concilier:
- Algorithmes de temps exponentiels doubles exécutés en temps avec constante
- Des algorithmes de temps exponentiels s'exécutent en avec constante
- La première borne croît plus vite que la seconde; c'est-à-dire qu'il existe des algorithmes qui fonctionnent en temps exponentiel double mais pas en temps exponentiel
- En appliquant à la double limite exponentielle, nous avons , qui tombe dans la limite exponentielle précédemment indiquée
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é.
Réponses:
Le problème se résume à une terminologie ambiguë.
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)n 22n
la source
a^b^c
et lance une erreur à la place.)la source