Y a-t-il des algorithmes O (1 / n)?

Question

Y a-t-il des algorithmes O (1 / n)?

Ou toute autre chose qui est inférieure à O (1)?

Answer 1

Cette question n'est pas aussi stupide que cela puisse paraître. Au moins théoriquement, quelque chose comme O(1/n) est entièrement sensible, lorsque nous prenons la définition mathématique de la notation Grand O:

Maintenant, vous pouvez facilement remplacer g(x) 1/x ... il est évident que la définition ci-dessus tient toujours pour certains f.

Aux fins de l'estimation asymptotique au moment de l'exécution de la croissance, c'est moins viable ... un véritable algorithme ne peut pas être plus rapide que l'entrée se développe. Bien sûr, vous pouvez construire l'arbitraire d'un algorithme pour réaliser, par exemple, la suivante:

def get_faster(list):
    how_long = (1 / len(list)) * 100000
    sleep(how_long)

Clairement, cette fonction passe moins de temps que la taille de saisie pousse ... au moins jusqu'à une certaine limite, imposé par le matériel (précision le nombre minimum de fois qu' sleep peut attendre, le temps de traiter les arguments etc.): cette limite serait alors une constante de la limite inférieure donc, en fait, la fonction ci-dessus encore a exécution O(1).

Mais il sont en fait dans le monde réel des algorithmes où le runtime peut diminuer (au moins partiellement) quand le signal d'entrée augmente. Notez que ces algorithmes ne pas exposer d'exécution comportement au-dessous de O(1), si. Encore, ils sont intéressants. Prenez, par exemple, le texte très simple de l'algorithme de recherche par Horspool. Ici, le moteur d'exécution diminue à mesure que la longueur du motif de recherche augmente (mais en augmentant la longueur de la botte de foin sera une fois de plus, augmenter d'exécution).

Answer 2

Oui.

Il y a précisément un algorithme d'exécution O(1/n), le "vide" de l'algorithme.

Pour un algorithme à temps O(1/n) signifie qu'il s'exécute à l'infini en moins d'étapes de l'algorithme consiste en une seule instruction. Si elle s'exécute en moins d'étapes qu'un pas pour tout n > n0, il doit comprendre précisément aucune instruction à tous pour ces. Depuis la vérification "si n > n0' frais au moins 1 instruction, il doit s'agir d'aucune instruction pour tout n.

En résumé: Le seul algorithme est O(1/n) est le vide de l'algorithme, composé d' aucune instruction.

Answer 3

Je pense que la source du débat est peut-être le tort de Grand-Oh et Grand-theta notations.

Des réponses et des commentaires qu'il a été mentionné qu'un O(1/n) peut être considérée O(1) que la fonction est déjà limité à quelques constante. C'est vrai et en effet, c'est la nature de la Grand-Oh notation. Vous pouvez dire QuickSort est O(n¹⁰⁰) et vous sont techniquement correct, car c'est un valide limite supérieure (ce qui n'est pas très serré dans cet exemple).

Ainsi, techniquement, cette question est évidente: Si quelque chose est à moins de O(1) (ou O(quoi que), d'ailleurs), il serait également être O(1) O(> quoi que ce soit)), par définition.

Dans les conversations régulières, nous utilisons essentiellement des Grands-Oh à dire serré limites (au lieu de Grand-thêta, qui est la bonne notation pour elle). Fondamentalement, la question ne doit pas inclure le "ou quoi que ce soit à moins de O(1)." Konrad réponse est complètement à droite.

Ces notations sont les concepts théoriques. Ils ne prennent pas une chose importante en compte qu'actuellement nous limite dans la pratique: Dans la pratique, nos machines sont finis et c'est là où il semble un paradoxe. Dans une partie limitée de la machine, notre "n" toujours a une limite supérieure. Par conséquent,"1/n" aura une limite inférieure qui est une constante. Si l'algorithme pratiquement regarde O(1) dans tous des machines à états finis , mais parce que notre n ne peut jamais devenir assez grand.

---

Pour ceux qui croient qu'il n'existe pas o(1) (petit-oh) des algorithmes dans la pratique (comme mentionné dans les réponses à certaines questions), je peut dire que, dans la pratique, tous les algorithmes que finalement l'arrêt sont également O(1). Avec le même raisonnement mentionné ci-dessus, car l'entrée est toujours borné, de toute fonction d'entrée sera également limitée (il peut être très grande, mais elle a toujours une constante liée!), ainsi, chaque algorithme est - O(1) dans la zone limitée de machines. (Autrement dit, casier principe implique que tous les déterministe de la machine à état fini avec S différents états que peut avoir au plus S transitions avant de revenir à l'état initial. Donc, n'importe quel algorithme qui finalement s'arrête, ce qui ne devrait pas faire de la machine à de retour à l'état de départ, peut avoir au plus S-1 les transitions de l'état, de sorte que chaque algorithme en O(1)).

---

Comme l'a souligné dans les commentaires, le calcul, tel que défini par le modèle de machine de Turing, est par nature discrets. Cela implique qu' 1/n algorithmes ne peuvent pas exister dans un discret modèle de calcul. Mon point est, lors de l'utilisation de l'asymptotique de la croissance sur la mise en œuvre pratique des algorithmes, nous sommes déjà en ignorant certaines limites (pour de bonnes raisons). Il peut y avoir des algorithmes avec la diminution du temps de course (jusqu'à ce qu'il atteigne une limite, bien sûr) que l'entrée grandit (comme Konrad dit). De même, on peut biaiser l'utilisation de la notation pour décrire le temps d'exécution d'une mise en œuvre d'un tel algorithme.

Answer 4

déchainée est correct, O(1) est la meilleure performance possible. Cependant, il n'implique pas une solution rapide, juste un moment fixe de la solution.

Une variante intéressante, et peut-être ce qui est vraiment suggéré, dont les problèmes plus facilement que la population augmente. Je ne peux penser à de 1, mais artificiel et de la langue-dans-joue réponse:

Faire deux personnes sont dans un ensemble ont la même date d'anniversaire? Lorsque n dépasse 365, retourner la valeur true. Bien que de moins de 365, c'est O(n ln n). Peut-être pas une grande réponse, puisque le problème n'est pas lentement obtenir plus facile, mais devient O(1) pour n > 365.

Answer 5

Ce n'est pas possible. La définition de Big-O n'est pas plus grande que l' inégalité:

 A(n) = O(B(n)) <=> exists constant C, C > 0 such that for all n A <= C*B
 

Donc B (n) est en fait la valeur maximale, donc si elle diminue à mesure que n augmente, l'estimation ne changera pas.