O(log N) == O(1) - Pourquoi pas ?

Question

Chaque fois que je considère des algorithmes/structures de données, j'ai tendance à remplacer les parties log(N) par des constantes. Oh, je sais que log(N) diverge - mais est-ce important dans les applications du monde réel ?

log(infini) < 100 à toutes fins utiles.

Je suis vraiment curieux de voir des exemples concrets où cela ne tient pas.

Pour clarifier :

• Je comprends O(f(N))
• Je suis curieux de connaître des exemples concrets où le asymptotique le comportement importe plus que le constantes de la performance réelle.
• Si log(N) peut être remplacé par une constante, il peut encore être remplacé par une constante en O( N log N).

Cette question a pour but (a) de me divertir et (b) de rassembler des arguments à utiliser si je me heurte (à nouveau) à une controverse sur les performances d'un modèle.

Answer 1

La notation du grand O vous renseigne sur la façon dont votre algorithme évolue avec une entrée croissante. O(1) signifie que la croissance de l'entrée n'a pas d'importance, l'algorithme sera toujours aussi rapide. O(logn) signifie que l'algorithme sera rapide, mais qu'il prendra un peu plus de temps au fur et à mesure que votre entrée augmentera.

O(1) et O(logn) font une grande différence lorsque l'on commence à combiner les algorithmes.

Prenons l'exemple des jointures avec index. Si vous pouviez faire une jointure en O(1) au lieu de O(logn), vous auriez des gains de performance énormes. Par exemple, avec O(1), vous pouvez effectuer n'importe quel nombre de jointures et vous obtenez toujours O(1). Mais avec O(logn), vous devez multiplier le nombre d'opérations par logn à chaque fois.

Pour les grandes entrées, si vous avez un algorithme qui est déjà O(n^2), vous préférez de loin faire une opération qui est O(1) à l'intérieur, et non O(logn) à l'intérieur.

N'oubliez pas non plus que Big-O de n'importe quoi peut avoir des frais généraux constants. Disons que cet overhead constant est de 1 million. Avec O(1), cette surcharge constante n'amplifie pas le nombre d'opérations autant que le fait O(logn).

Un autre point est que tout le monde pense à O(logn) pour représenter n éléments d'une structure de données en arbre par exemple. Mais cela pourrait être n'importe quoi, y compris des octets dans un fichier.

Answer 2

Je pense que c'est une approche pragmatique ; O(logN) ne sera jamais supérieur à 64. En pratique, lorsque les termes deviennent aussi "petits" que O(logN), il faut mesurer pour voir si les facteurs constants l'emportent. Voir aussi

http://stackoverflow.com/questions/1424303/uses-of-ackermann-function/1424397#1424397

Pour me citer dans les commentaires d'une autre réponse :

[L'"analyse" n'est importante que pour les facteurs qui sont au moins O(N). Pour tout facteur facteur plus petit, l'analyse big-oh est inutile et vous devez mesurer.

et

"Avec O(logN) votre taille d'entrée n'est pas importe." C'est tout le sens de la la question. Bien sûr que ça compte... en théorie . La question que pose le PO est de savoir si cela importe en pratique ? I prétends que la réponse est non, il n'y a pas il n'y a pas, et il n'y aura jamais, un ensemble de données pour lequel le logN croîtra si vite qu'il pourra toujours être battu par un algorithme en temps constant. Même pour le plus grand ensemble de données pratiques imaginables à l'époque vie de nos petits-enfants, un algorithme logN a une bonne chance de battre un algorithme en temps constant - vous devez toujours mesurer.

EDIT

Une bonne discussion :

http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

À peu près à mi-chemin, Rich discute des essais de hachage de Clojure, qui sont clairement O(logN), mais la base du logarithme est grande et donc la profondeur du trie est au plus 6 même s'il contient 4 milliards de valeurs. Ici, "6" est toujours une valeur O(logN), mais c'est une valeur incroyablement petite, et donc choisir de rejeter cette structure de données impressionnante parce que "j'ai vraiment besoin de O(1)" est une chose stupide à faire. Cela souligne combien la plupart des autres réponses à cette question sont simplement mauvais du point de vue du pragmatique qui veut que son algorithme "fonctionne rapidement" et "s'adapte bien", indépendamment de ce que dit la "théorie".

EDIT

Voir aussi

http://queue.acm.org/detail.cfm?id=1814327

qui dit

A quoi sert un algorithme O(log2(n)) si ces opérations provoquent des défauts de page et ralentissent les opérations sur le disque ? Pour la plupart des ensembles de données pertinents, un algorithme O(n) ou même un algorithme O(n^2), qui évite les défauts de page, le surpasse. page, le surpasse.

(mais allez lire l'article pour le contexte).

Answer 3

Il s'agit d'une erreur courante - rappelez-vous que la notation Big O ne vous renseigne PAS sur les performances absolues d'un algorithme à une valeur donnée, elle vous indique simplement le comportement d'un algorithme à mesure que vous augmentez la taille de l'entrée.

Lorsque vous le prenez dans ce contexte, il devient clair pourquoi un algorithme A ~ O(logN) et un algorithme B ~ O(1) sont différents :

si j'exécute A sur une entrée de taille a, puis sur une entrée de taille 1000000*a, je peux m'attendre à ce que la deuxième entrée prenne log(1 000 000) fois plus de temps que la première.

si j'exécute B sur une entrée de taille a, puis sur une entrée de taille 1000000*a, je peux m'attendre à ce que la deuxième entrée prenne à peu près le même temps que la première.

EDIT : En réfléchissant un peu plus à votre question, je pense qu'il y a une certaine sagesse à y trouver. Bien que je ne dirais jamais qu'il est correct de dire O(lgN) == O(1), il est possible d'en tirer des conclusions. IS Il est possible qu'un algorithme O(lgN) soit utilisé plutôt qu'un algorithme O(1). Cela nous ramène à la question des performances absolues évoquée plus haut : Le simple fait de savoir qu'un algorithme est O(1) et qu'un autre algorithme est O(lgN) n'a rien à voir avec les performances absolues. PAS Il n'est pas suffisant de déclarer que vous devriez utiliser O(1) plutôt que O(lgN), il est certainement possible, étant donné votre gamme d'entrées possibles, qu'un O(lgN) vous convienne mieux.

Answer 4

Vous avez demandé un exemple concret. Je vais vous en donner un. La biologie computationnelle. Un brin d'ADN codé en ASCII représente quelque chose de l'ordre du gigaoctet dans l'espace. Une base de données typique comptera évidemment plusieurs milliers de ces brins.

Or, dans le cas d'un algorithme d'indexation/de recherche, ce multiple de log(n) fait une grande différence lorsqu'il est associé à des constantes. Pourquoi ? Il s'agit de l'une des applications où la taille de votre entrée est astronomique. De plus, la taille de l'entrée continuera toujours à augmenter.

Certes, ce type de problèmes est rare. Il n'y a qu'un nombre limité d'applications de cette taille. Dans ces circonstances, cependant... cela fait une grande différence.

Answer 5

L'égalité, telle que vous la décrivez, est un abus courant de la notation.

Pour clarifier : nous écrivons généralement f(x) = O(logN) pour impliquer "f(x) est O(logN)".

En tout cas, O(1) signifie un nombre constant d'étapes/temps (comme limite supérieure) pour effectuer une action, quelle que soit la taille de l'ensemble d'entrée. Mais pour O(logN) Le nombre de pas/temps croît toujours en fonction de la taille de l'entrée (le logarithme de celle-ci), mais très lentement. Pour la plupart des applications du monde réel, vous pouvez supposer sans risque que ce nombre d'étapes ne dépassera pas 100, mais je parierais qu'il existe de multiples exemples d'ensembles de données suffisamment grands pour rendre votre affirmation à la fois dangereuse et nulle (traces de paquets, mesures environnementales, et bien d'autres).