Grande notation O imbriquée

Disons que j'ai un graphique $|G|$ avec $|E|=O(V^2)$bords. Je veux exécuter BFS sur$G$ qui a une durée de $O(V+E)$.

Il semble naturel d'écrire que le temps d'exécution sur ce graphique serait $O(O(V^2)+V)$ puis simplifier pour $O(V^2)$.

Y a-t-il des pièges à utiliser un tel raccourci "supprimer-le-nested-O" (pas seulement dans ce cas, mais plus généralement)?

Permettez-moi de commencer par une recommandation: traiter la notation Landau comme vous (devriez) traiter l'arrondi: arrondir rarement, arrondir tard. Si vous savez quelque chose de plus précis que$O(.)$, utilisez-le jusqu'à ce que vous ayez terminé tous les calculs, et Landauify à la fin.

---

Quant à la question, creusons cet abus de notation¹. Comment interpréterions-nous quelque chose comme$h \in O(f + O(g))$? Nous devons remplacer$O$avec sa définition de l'intérieur. Donc, nous obtenons

$\qquad \displaystyle \exists g' \in O(g).\, h \in O(f + g')$

et alors

$\qquad \displaystyle \exists g' \in O(g).\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + g'(n))$

ce qui équivaut à

$\qquad \displaystyle \exists c > 0.\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + cg(n))$.

Comme certainement² $d(f(n) + cg(n)) \leq cd(f(n) + g(n))$, nous voyons que cela équivaut à $h \in O(f + g)$; la perte de précision est ignorée par$O$ en tous cas.

---

Qu'en est-il des autres combinaisons, disons $h \in O(f + \Omega(g))$? Si nous essayons la même chose ici, nous obtenons

$\qquad \displaystyle \exists g' \in \Omega(g).\, h \in O(f + g')$.

Mais c'est une tautologie: $h$est certainement délimité au-dessus par quelque chose d’arbitrairement grand. Donc, combiner les limites supérieures et inférieures de cette manière n'a pas de sens.

---

1. $O(.)$et les autres symboles Landau mappent les fonctions aux classes de fonctions. Le nourrir d'une classe de fonction n'est pas immédiatement significatif.
2. Du moins si nous considérons uniquement les fonctions positives, que nous pouvons assumer en toute sécurité lorsque nous parlons de temps d'exécution. Je ne suis pas sûr que cela fonctionne en général.

Je voulais juste ajouter ceci parce que je l'ai rencontré récemment. Bien que ce raccourci soit parfait avec l'addition et la multiplication (lorsqu'il ne mélange pas$O$ avec $\Omega$; voir la réponse acceptée), des précautions doivent être prises lors de l'utilisation d'exposants. Par exemple:

$$O(n^{O(m)}) \not= O(n^m).$$ Dans cet exemple, $n^{2m}$ appartient à la première classe mais pas à la seconde.

Par définition, $O(g)$ est un ensemble et si vous utilisez cette notation imbriquée, vous auriez un ensemble dans un ensemble, ce qui serait faux.

La définition de la notation O

$O(g) = \left \lbrace f|\exists c > 0\exists x_0>0 \forall x > x_0: |f(x)| \leq c *|g(x)|\right \rbrace$

L'erreur

Vous avez utilisé des termes comme $O(O(n)+k)$ où k et n sont des fonctions et $O(n)$est un ensemble. Mais quel est le résultat d'une fonction ajoutée à un ensemble? Ce n'est pas défini!

Version correcte

Au lieu d'utiliser les symboles Landau imbriqués, vous pouvez effectuer les opérations suivantes: $O(m+k),m \in O(n)$

Dans la section 9.3 "$O$Manipulation "du livre Concrete Mathematics (Second Edition), Knuth a énuméré quelques règles de manipulation sur le$O$-notation (Dans ce qui suit, je suppose que les deux $f(n)$ et $g(n)$sont positifs; notez que l'ordre des règles a été modifié).

$$\begin{gather} (1). \quad n^m = O(n^{m'}), \quad m \le m' \\ (3). \quad f(n) = O(f(n)) \\ (5). \quad O(O(f(n))) = O(f(n)) \\ (4). \quad c \cdot O(f(n)) = O(f(n)) \\ (2). \quad O(f(n)) + O(g(n)) = O(f(n) + g(n)) \\ (6). \quad O(f(n)) O(g(n)) = O(f(n) g(n)) = f(n) O(g(n))\\ \end{gather}$$

By (3), you can wrap/unwrap a function $f(n)$ with an O-notation. Then by (5), you can actually wrap/unwrap (or called, nest) it arbitrarily finite times. Using (4), you can also add/remove constant multiplication factors to/from $O$.

Then, (2) and (6) allow you to manipulate nested $O$-notations in the way compatible with $+$ and $\times$.