Y a-t-il toujours une complexité Big Oh strictement entre deux autres?

J'apprends l'analyse asymptotique et j'ai vu des complexités d'aspect exotique vivre entre d'autres courantes. Par exemple, "log log n" est strictement compris entre 1 et log n. Je me demande si l'on peut toujours trouver des complexités entre deux autres.

Plus précisément, pour toutes les fonctions f et g avec O (f) ⊂ O (g), existe-t-il toujours un h tel que O (f) ⊂ O (h) ⊂ O (g)?

Ce ne sont pas des devoirs ou quoi que ce soit. Je suis juste curieux de savoir si quelqu'un sait.

Oui: prenez une fonction au milieu, pour une définition appropriée du milieu. Vous avez un large choix.

Si $O(f) \subset O(g)$ (où l'inclusion est stricte), puis $g \in O(g) \setminus O(f)$ (parce que si $g \in O(f)$ et $f \in O(g)$ puis $\Theta(f) = \Theta(g)$). Prenez la moyenne géométrique: laissez$h = \sqrt{f \cdot g}$ (puisque nous parlons ici de complexité, je suppose que les fonctions sont positives).

alors $f \in O(h)$ et $h \in O(g)$ (si cela n'est pas immédiatement évident, prouvez-le en utilisant la définition de $O$), c'est à dire $O(f) \subseteq O(h) \subseteq O(g)$. Si$O(f) = O(h)$ puis $g = f \in O(f)$, ce qui n'est pas le cas puisque nous avons supposé $g \notin O(f)$. Reste à prouver que$O(h) \ne O(g)$et nous aurons $O(f) \subset O(h) \subset (g)$.

Si $O(h) = O(g)$ puis $g \in O(h)$, c'est-à-dire qu'il existe $A$ et $C \gt 0$ tel que $\forall x \ge A, g(x) \le C \, h(x) = C \sqrt{f(x) g(x)}$. alors$g(x) \le C^2 f(x)$ (prenez le carré et divisez par $g(x)$; encore une fois, je suppose des fonctions positives), donc$g \in O(f)$, ce qui va à l'encontre de notre hypothèse initiale. L'hypothèse$O(h) = O(g)$ conduit à une contradiction, qui conclut la preuve.

cela semble être vrai pour les fonctions "bien définies" ou éventuellement "constructibles espace / temps", mais il est connu que certaines ("certaines" fonctions "pathologiques") sont trouvées par Blum dans par exemple le théorème de Blums Gap pour lequel il n'est pas le Cas. il semble donc similaire au concept de différenciation, par exemple, dans le calcul qui fonctionne pour les "fonctions les mieux comportées" mais qui ont trouvé des "exceptions pathologiques". il ne semble pas y avoir beaucoup d'étude systématique / approfondie jusqu'à présent de ces "exceptions pathologiques" dans la théorie de la complexité.