La complexité temporelle de l'algorithme vide est-elle O(0) ?

Question

Donc, étant donné le programme suivant :

---

La complexité temporelle de ce programme est-elle O(0) ? En d'autres termes, est-ce que 0 est O(0) ?

J'ai pensé que le fait de répondre à cette question dans un document séparé permettrait d'éclaircir les points suivants cette question .

EDIT : Beaucoup de bonnes réponses ici ! Nous sommes tous d'accord pour dire que 0 est O(1). La question est : 0 est-il également O(0) ?

Answer 1

De Wikipedia :

La description d'une fonction en termes de notation du grand O ne fournit généralement qu'une limite supérieure du taux de croissance de la fonction.

D'après cette description, puisque l'algorithme vide nécessite 0 temps d'exécution, il a une performance supérieure de O(0). Cela signifie qu'il est également O(1), qui se trouve être une limite supérieure plus grande.

Modifier :

Plus formellement à partir de CLR (1ed, pg 26) :

Pour une fonction donnée g ( n ), nous désignons O ( g ( n )) l'ensemble des fonctions

O ( g ( n )) = { f ( n ) : il existe des constantes positives c et n ₀ telle que 0 ≤ f(n) ≤ cg ( n ) pour tous les n ≥ n ₀ }

La performance en temps asymptotique de l'algorithme vide, s'exécutant en temps 0 quelle que soit l'entrée, est donc membre de O (0).

Edit 2 :

Nous sommes tous d'accord pour dire que 0 est O(1). La question est de savoir si 0 est également O(0).

Sur la base des définitions, je dis oui.

De plus, je pense que la question est un peu plus importante que ce que les réponses indiquent. En soi, l'algorithme vide est probablement dénué de sens. Cependant, chaque fois qu'un algorithme non trivial est spécifié, on peut considérer que l'algorithme vide se trouve entre les étapes consécutives de l'algorithme spécifié, ainsi qu'avant et après les étapes de l'algorithme. Il est agréable de savoir que le "néant" n'a pas d'incidence sur les performances de l'algorithme en temps asymptotique.

Edit 3 :

Adam Crume fait ce qui suit réclamation :

Pour toute fonction f ( x ), f ( x ) est dans O( f ( x )).

Preuve : let S soit un sous-ensemble de R et T soit un sous-ensemble de R * (les nombres réels non négatifs) et soit f ( x ): S -> T et c ≥ 1. Alors 0 ≤ f ( x ) ≤ f ( x ) qui conduit à 0 ≤ f ( x ) ≤ cf ( x ) pour tout x∈ S . Par conséquent, f ( x ) ∈ O( f ( x )).

Plus précisément, si f ( x ) = 0 alors f ( x ) ∈ O(0).

Answer 2

Il prend le même temps d'exécution quelle que soit l'entrée, il est donc O(1) par définition.

Answer 3

Plusieurs réponses disent que la complexité est O(1) parce que le temps est une constante et que le temps est limité par le produit d'un certain coefficient et de 1. Eh bien, il est vrai que le temps est une constante et qu'il est limité de cette façon, mais cela ne signifie pas que la meilleure réponse est O(1).

Considérons un algorithme qui s'exécute en temps linéaire. Il est ordinairement désigné comme O(n) mais jouons l'avocat du diable. Le temps est limité par le produit d'un certain coefficient et de n^2. Si nous considérons O(n^2) comme un ensemble, l'ensemble de tous les algorithmes dont la complexité est suffisamment petite, alors les algorithmes linéaires sont dans cet ensemble. Mais cela ne signifie pas que la meilleure réponse est O(n^2).

L'algorithme vide est en O(n^2) et en O(n) et en O(1) et en O(0). Je vote pour O(0).

Answer 4

J'ai un argument très simple pour que l'algorithme vide soit O(0) : Pour toute fonction f(x), f(x) est dans O(f(x)). Laissez simplement f(x)=0, et nous avons que 0 (le temps d'exécution de l'algorithme vide) est dans O(0).

Au passage, je déteste quand les gens écrivent f(x) = O(g(x)), alors que ça devrait être f(x) ∈ O(g(x)).

Answer 5

Le grand O est la notation asymptotique. Pour utiliser le grand O, vous avez besoin d'un fonction - en d'autres termes, l'expression doit être paramétrée par n, même si n n'est pas utilisé. Cela n'a aucun sens de dire que le nombre 5 est O(n), c'est la fonction constante f(n) = 5 qui est O(n).

Donc, pour analyser la complexité temporelle en termes de grand O, vous avez besoin d'une fonction de n. Votre algorithme fait toujours des étapes discutables 0, mais sans un paramètre variable, parler de comportement asymptotique n'a aucun sens. Supposons que votre algorithme soit paramétré par n. Ce n'est que maintenant que vous pouvez utiliser la notation asymptotique. Cela n'a aucun sens de dire qu'il est O(n 2 ), ou même O(1), si vous ne spécifiez pas ce qu'est n (ou la variable cachée dans O(1)) !

Dès que l'on a fixé le nombre d'étapes, c'est une question de définition du grand O : la fonction f(n) = 0 est O(0).

Comme il s'agit d'une question de bas niveau, elle dépend du modèle de calcul. Dans des hypothèses "idéalistes", il est possible que vous ne fassiez rien. Mais en Python, vous ne pouvez pas dire def f(x): mais seulement def f(x): pass . Si vous supposez que chaque instruction, même pass (NOP), prend du temps, alors la complexité est f(n) = c pour une certaine constante c, et à moins que c != 0 vous pouvez seulement dire que f est O(1), et non O(0).

Il convient de noter que le grand O en soi n'a rien à voir avec les algorithmes. Par exemple, vous pouvez dire sin x = x + O(x 3 ) lors de la discussion de l'expansion de Taylor. De plus, O(1) ne signifie pas constant, mais limité par une constante.