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

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 (infinity) <100 à toutes fins utiles.

Je suis vraiment curieux de connaître des exemples concrets où cela ne tient pas.

Clarifier:

  • Je comprends o (f (n))
  • Je suis curieux des exemples du monde réel où le comportement asymptotique compte plus que les constantes de la performance réelle.
  • Si log (N) peut être remplacé par une constante, il peut toujours être remplacé par une constante dans O (N log N).

Cette question est pour (a) divertissement et (b) rassembler des arguments à utiliser si je cours (encore) dans une controverse sur la performance d’un design.

Je pense que c’est une approche pragmatique; O (logN) ne sera jamais supérieur à 64. En pratique, chaque fois que les termes sont aussi petits que O (logN), vous devez mesurer pour voir si les facteurs constants l’emportent. Voir également

Utilisations de la fonction Ackermann?

Pour me citer des commentaires sur une autre réponse:

[Big-Oh] “Analyse” ne concerne que les facteurs qui sont au moins O (N). Pour tout facteur plus petit, l’parsing Big Oh est inutile et vous devez mesurer.

et

“Avec O (logN), la taille de votre entrée est importante.” C’est tout l’intérêt de la question. Bien sûr que c’est important … en théorie . La question posée par l’OP est la suivante: est-ce important dans la pratique ? Je soutiens que la réponse est non, il n’y a pas, et ne le sera jamais, un dataset pour lequel logN augmentera si rapidement qu’il sera toujours battu par un algorithme à temps constant. Même pour le plus grand dataset pratiques imaginables au cours de la vie de nos petits-enfants, un algorithme logN a de bonnes chances de battre un algorithme à temps constant – vous devez toujours mesurer.

MODIFIER

Une bonne conversation:

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

à mi-chemin, Rich discute des tentatives de hachage de Clojure, qui sont clairement O (logN), mais la base du logarithme est grande et la profondeur du sortinge est au maximum de 6, même si elle contient 4 milliards de valeurs. Ici, “6” est toujours une valeur O (logN), mais c’est une valeur incroyablement petite, et choisir de supprimer cette structure de données géniale 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 erronées du sharepoint vue du pragmatiste qui veut que son algorithme “tourne vite” et “évolue bien”, indépendamment de ce que dit la “théorie”.

MODIFIER

Voir également

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 des opérations sur disque lent? Pour la plupart des ensembles de données pertinents, un algorithme O (n) ou même O (n ^ 2), qui évite les défauts de page, exécutera des cercles autour de lui.

(mais lisez l’article pour contexte).

La notation Big O vous indique comment votre algorithme change avec les entrées croissantes. O (1) vous dit que votre consortingbution n’a pas d’importance, l’algorithme sera toujours aussi rapide. O (logn) dit que l’algorithme sera rapide, mais à mesure que vos entrées augmenteront, cela prendra un peu plus de temps.

O (1) et O (logn) font une grande différence lorsque vous commencez à combiner des algorithmes.

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

Pour les entrées de grande taille, si vous aviez déjà un algorithme O (n ^ 2), vous préféreriez plutôt faire une opération O (1) à l’intérieur, et non pas O (logn) à l’intérieur.

Rappelez-vous également que Big-O de tout peut avoir une surcharge constante. Disons que les frais généraux constants sont de 1 million. Avec O (1), cette surcharge constante n’amplifie pas le nombre d’opérations autant que O (logn).

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

C’est une erreur courante – rappelez-vous que la notation Big O ne vous dit PAS la performance absolue d’un algorithme à une valeur donnée, mais simplement le comportement d’un algorithme lorsque vous augmentez la taille de l’entrée.

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

si je lance A sur une entrée de taille a, alors sur une entrée de taille 1000000 * a, je peux espérer que la seconde entrée prenne log (1 000 000) fois plus longtemps que la première entrée

si je lance B sur une entrée de taille a, alors sur une entrée de taille 1000000 * a, je peux espérer que la seconde entrée prenne à peu près le même temps que la première entrée

EDIT : En réfléchissant un peu plus à votre question, je pense qu’il y a une certaine sagesse à y avoir. Alors que je ne dirais jamais que c’est correct de dire O (lgN) == O (1), il est possible qu’un algorithme O (lgN) puisse être utilisé sur un algorithme O (1). Cela revient au point sur les performances absolues ci-dessus: la connaissance d’un seul algorithme est O (1) et un autre algorithme est O (lgN) n’est pas suffisant pour déclarer que vous devez utiliser le O (1) sur O (lgN) possible compte tenu de votre gamme d’entrées possibles, un O (lgN) pourrait mieux vous servir.

Vous avez demandé un exemple concret. Je vais vous en donner un. Biologie computationnelle. Un brin d’ADN codé en ASCII est quelque part au niveau des gigaoctets dans l’espace. Une firebase database type comportera évidemment plusieurs milliers de brins de ce type.

Maintenant, dans le cas d’un algorithme d’indexation / recherche, ce multiple de log (n) fait une grande différence lorsqu’il est associé à des constantes. La raison pour laquelle? C’est l’une des applications où la taille de votre saisie est astronomique. En outre, la taille de l’entrée continuera à augmenter.

Certes, ces types de problèmes sont rares. Il y a tellement d’applications que cela est grand. Dans ces circonstances, cependant … cela fait un monde de différence.

L’égalité, comme vous le décrivez, est un abus de notation commun.

Pour clarifier: nous écrivons habituellement f (x) = O (logN) pour impliquer que “f (x) est O (logN)”.

En tout état de cause, O(1) signifie un nombre constant d’étapes / temps (en tant que 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 celui-ci), il augmente simplement très lentement. Pour la plupart des applications du monde réel, vous pouvez supposer que ce nombre d’étapes ne dépasse pas 100, mais je parie qu’il existe plusieurs exemples de jeux de données suffisamment importants pour que votre déclaration soit dangereuse et vide (traces de paquets, mesures environnementales et beaucoup plus).

Pour assez petit N, O (N ^ N) peut en pratique être remplacé par 1. Pas O (1) (par définition), mais pour N = 2 vous pouvez le voir comme une opération avec 4 parties, ou une constante de temps opération.

Et si toutes les opérations duraient une heure? La différence entre O (log N) et O (1) est alors grande, même avec un petit N.

Ou si vous devez exécuter l’algorithme dix millions de fois? Ok, cela a pris 30 minutes, alors quand je l’exécute sur un dataset cent fois plus gros, cela devrait prendre 30 minutes car O (logN) est “le même” que O (1) …. hein … quoi?

Votre déclaration que “je comprends O (f (N))” est clairement fausse.

Des applications du monde réel, oh … je ne sais pas … CHAQUE UTILISATION DE O () – notation JAMAIS?

Recherche binary dans une liste sortingée de 10 millions d’éléments par exemple. C’est la raison même pour laquelle nous utilisons des tables de hachage lorsque les données sont suffisamment volumineuses. Si vous pensez que O (logN) est le même que O (1), alors pourquoi utiliseriez-vous JAMAIS un hachage au lieu d’un arbre binary?

Comme beaucoup l’ont déjà dit, pour le monde réel, il faut d’abord examiner les facteurs constants avant même de s’inquiéter des facteurs de O (log N).

Ensuite, considérez ce que vous attendez de N. Si vous avez de bonnes raisons de penser que N <10, vous pouvez utiliser une recherche linéaire plutôt que binaire. C'est O (N) au lieu de O (log N), qui selon vos lumières serait significatif – mais une recherche linéaire qui déplace les éléments trouvés vers l’avant peut bien surpasser un arbre équilibré plus compliqué, selon l’application .

D’un autre côté, notez que, même si le log N ne devrait pas dépasser 50, un facteur de performance de 10 est vraiment énorme – si vous êtes lié au calcul, un facteur comme celui-ci peut facilement créer ou défaire votre application. Si cela ne vous suffit pas, vous verrez fréquemment des facteurs de (log N) ^ 2 ou (logN) ^ 3 dans les algorithmes. Même si vous pensez pouvoir ignorer un facteur de (log N), cela ne signifie pas vous pouvez en ignorer davantage.

Enfin, notons que l’algorithme du simplexe pour la programmation linéaire a les performances les plus défavorables de O (2 ^ n). Cependant, pour des problèmes pratiques, le pire des cas ne se présente jamais; en pratique, l’algorithme simplex est rapide, relativement simple et par conséquent très populaire.

Il y a environ 30 ans, quelqu’un a développé un algorithme à temps polynomial pour la programmation linéaire, mais ce n’était pas pratique au départ car le résultat était trop lent .

De nos jours, il existe des algorithmes alternatifs pratiques pour la programmation linéaire (avec un temps de propagation polynomial, pour ce que cela vaut), qui peut surpasser la méthode simplex en pratique. Mais, selon le problème, la méthode simplex rest compétitive.

L’observation que O(log n) est souvent indiscernable de O(1) est une bonne.

Comme exemple familier, supposons que nous voulions trouver un seul élément dans un tableau sortingé de 1 000 000 000 000 d’éléments:

  • avec la recherche linéaire, la recherche prend en moyenne 500 000 000 000 d’étapes
  • avec la recherche binary, la recherche prend en moyenne 40 étapes

Supposons que nous ajoutions un seul élément au tableau que nous recherchons, et maintenant nous devons rechercher un autre élément:

  • avec la recherche linéaire, la recherche prend en moyenne 500 000 000 001 étapes (changement indiscernable)
  • avec une recherche binary, la recherche prend en moyenne 40 étapes (changement indiscernable)

Supposons que nous ayons doublé le nombre d’éléments dans le tableau que nous recherchons, et maintenant nous devons rechercher un autre élément:

  • Avec la recherche linéaire, la recherche prend en moyenne 1 000 000 000 000 d’étapes (changement remarquable)
  • avec la recherche binary, la recherche prend en moyenne 41 étapes (changement indiscernable)

Comme nous pouvons le voir à partir de cet exemple, à toutes fins utiles, un algorithme O(log n) tel que la recherche binary est souvent indiscernable d’un algorithme O(1) comme l’omniscience.

Le point à retenir est le suivant: * nous utilisons des algorithmes O(log n) car ils sont souvent indiscernables du temps constant et parce qu’ils sont souvent plus performants que les algorithmes de temps linéaire.

Évidemment, ces exemples supposent des constantes raisonnables. Evidemment, ce sont des observations génériques et ne s’appliquent pas à tous les cas. Évidemment, ces points s’appliquent à la fin asymptotique de la courbe, pas à la fin de n=3 .

Mais cette observation explique pourquoi, par exemple, nous utilisons des techniques telles que le réglage d’une requête pour effectuer une recherche d’index plutôt qu’une parsing de table – car une recherche d’index fonctionne à peu près constante quelle que soit la taille du jeu de données. écrasement lent sur des ensembles de données suffisamment grands. La recherche d’index est O(log n) .

Vous pourriez être intéressé par Soft-O, qui ignore le coût logarithmique. Cochez ce paragraphe dans Wikipedia.

Que voulez-vous dire par “oui” ou non?

Si vous êtes confronté au choix d’un algorithme O(1) et d’un algorithme O(lg n) , vous ne devez pas supposer qu’ils sont égaux. Vous devez choisir le temps constant. Pourquoi pas vous?

Et si aucun algorithme à temps constant n’existe, le temps logarithmique est généralement le meilleur que vous puissiez obtenir. Encore une fois, est-ce important ? Il suffit de prendre le plus rapidement possible.

Pouvez-vous me donner une situation où vous gagneriez quelque chose en définissant les deux comme égales? Au mieux, cela ne ferait aucune différence et, au pire, vous cacheriez de réelles caractéristiques d’évolutivité. Parce que généralement, un algorithme à temps constant sera plus rapide qu’un algorithme logarithmique.

Même si, comme vous le dites, lg(n) < 100 à toutes fins pratiques, cela rest un facteur 100 en plus de vos autres frais généraux. Si j'appelle votre fonction, N fois, alors cela commence à être important si votre fonction exécute un temps logarithmique ou une constante, car la complexité totale est alors O(n lg n) ou O(n) .

Donc, plutôt que de demander si "il est important" que vous supposiez que la complexité logarithmique soit constante dans "le monde réel", je vous demanderais si cela peut être utile.

Souvent, vous pouvez supposer que les algorithmes logarithmiques sont assez rapides , mais que gagnez-vous en les considérant constants?

O (logN) * ​​O (logN) * ​​O (logN) est très différent. O (1) * O (1) * O (1) est toujours constant. De même, un simple style de sorting rapide (nlogn) est différent de O (n O (1)) = O (n). Essayez de sortinger les éléments 1000 et 1000000. Ce dernier n’est pas 1000 fois plus lent, c’est 2000 fois, car log (n ^ 2) = 2log (n)

Le titre de la question est trompeur (bien choisi pour susciter le débat, attention).

O (log N) == O (1) est évidemment faux (et l’affiche en est consciente). La notation Big O, par définition, concerne l’parsing asymptotique. Lorsque vous voyez O (N), N est pris pour s’approcher de l’infini. Si N est assigné à une constante, ce n’est pas Big O.

Notez qu’il ne s’agit pas seulement d’un détail délicat que seuls les informaticiens théoriques doivent prendre en compte. Toute l’arithmétique utilisée pour déterminer la fonction O pour un algorithme repose sur elle. Lorsque vous publiez la fonction O pour votre algorithme, vous pouvez omettre beaucoup d’informations sur ses performances.

L’parsing Big O est cool, car elle vous permet de comparer des algorithmes sans se perdre dans des problèmes spécifiques à la plateforme (tailles de mots, instructions par opération, vitesse de la mémoire et vitesse du disque). Lorsque N passe à l’infini, ces problèmes disparaissent. Mais lorsque N est égal à 10000, 1000, 100, ces problèmes, ainsi que toutes les autres constantes que nous avons omises de la fonction O, commencent à avoir de l’importance.

Pour répondre à la question de l’affiche: O (log N)! = O (1), et vous avez raison, les algorithmes avec O (1) ne sont parfois guère meilleurs que les algorithmes avec O (log N), en fonction de la taille de l’entrée, et toutes les constantes internes qui ont été omises lors de l’parsing Big O.

Si vous savez que vous allez augmenter N, utilisez l’parsing Big O. Si vous ne l’êtes pas, vous aurez besoin de tests empiriques.

En théorie

Oui, dans des situations pratiques, log (n) est limité par une constante, nous dirons 100. Cependant, remplacer log (n) par 100 dans les situations où il est correct jette toujours des informations, ce qui rend la limite supérieure des opérations que vous avez calculé plus lâche et moins utile. Si vous remplacez un O (log (n)) par un O (1) dans votre parsing, votre cas n peut être 100 fois pire que ce que vous espériez. Votre parsing théorique aurait pu être plus précise et aurait pu prévoir un problème avant que vous ayez construit le système.

Je dirais que le but pratique de l’parsing big-O est d’essayer de prédire le temps d’exécution de votre algorithme le plus tôt possible. Vous pouvez simplifier votre parsing en biffant les termes log (n), mais vous avez ensuite réduit le pouvoir prédictif de l’estimation.

En pratique

Si vous lisez les articles originaux de Larry Page et de Sergey Brin sur l’architecture de Google, ils parlent d’utiliser des tables de hachage pour tout faire pour que, par exemple, la recherche d’une page Web mise en cache ne nécessite qu’une recherche sur disque dur. Si vous avez utilisé des index B-tree pour rechercher, vous pourriez avoir besoin de quatre ou cinq disques durs pour effectuer une recherche non mise en cache [*]. Le quadruplement de vos besoins en disque sur le stockage de votre page Web en cache mérite d’être envisagé d’un sharepoint vue professionnel et prévisible si vous ne rejetez pas tous les termes O (log (n)).

PS Je suis désolé d’utiliser Google comme exemple, ils sont comme Hitler dans la version informatique de la loi de Godwin .

[*] En supposant que 4 Ko soient lus depuis le disque, 100 milliards de pages Web dans l’index, ~ 16 octets par clé dans un nœud B-tree.

Comme d’autres l’ont souligné, Big-O vous explique comment évolue la performance de votre problème. Croyez-moi, c’est important. J’ai rencontré plusieurs fois des algorithmes qui étaient tout simplement terribles et qui ne répondaient pas aux demandes des clients car ils étaient trop lents. Comprendre la différence et trouver une solution O (1) est une amélioration considérable.

Cependant, bien sûr, ce n’est pas tout – par exemple, vous remarquerez que les algorithmes de sorting rapide basculeront toujours vers le sorting par insertion pour les petits éléments (Wikipedia dit 8-20) en raison du comportement des deux algorithmes sur les petits ensembles de données.

Il s’agit donc de comprendre les compromis que vous allez faire, ce qui implique une compréhension approfondie du problème, de l’architecture et de l’expérience à comprendre et de la manière d’ajuster les constantes impliquées.

Personne ne dit que O (1) est toujours meilleur que O (log N). Cependant, je peux vous garantir qu’un algorithme O (1) sera également amélioré, donc même si vous faites des suppositions incorrectes sur le nombre d’utilisateurs sur le système ou la taille des données à traiter, cela n’aura aucune importance. à l’algorithme

Oui, log (N) <100 pour la plupart des raisons pratiques, et Non, vous ne pouvez pas toujours le remplacer par une constante.

Par exemple, cela peut entraîner de graves erreurs lors de l’estimation des performances de votre programme. Si le programme O (N) a traité un tableau de 1 000 éléments en 1 ms, vous êtes sûr qu’il traitera 10 6 éléments en une seconde (ou plus). Si, cependant, le programme est O (N * logN), cela prendra environ 2 secondes pour traiter 10 6 éléments. Cette différence peut être cruciale – par exemple, vous pouvez penser que vous avez suffisamment de puissance serveur car vous recevez 3000 requêtes par heure et vous pensez que votre serveur peut gérer jusqu’à 3600 requêtes.

Un autre exemple. Imaginez que vous ayez la fonction f () fonctionnant dans O (logN), et à chaque fonction d’appel itération g (), qui fonctionne également dans O (logN). Ensuite, si vous remplacez les deux journaux par des constantes, vous pensez que votre programme fonctionne en temps constant. La réalité sera cruelle si – deux journaux peuvent vous donner jusqu’à 100 * 100 multiplicateurs.

Les règles de détermination de la notation Big-O sont plus simples lorsque vous ne décidez pas que O (log n) = O (1).

Comme krzysio l’a dit, vous pouvez accumuler des O (log n) s et ils feront alors une différence très notable. Imaginez que vous fassiez une recherche binary: O (log n) comparaisons, puis imaginez la complexité de chaque comparaison O (log n). Si vous négligez les deux, vous obtenez O (1) au lieu de O (log 2 n). De même, vous pouvez arriver à O (log 10 n) et vous remarquerez alors une grande différence pour pas trop grand “n” s.

Supposons que, dans l’ensemble de votre application, un algorithme représente 90% du temps que l’utilisateur attend pour l’opération la plus courante.

Supposons qu’en temps réel, l’opération O (1) prend une seconde sur votre architecture et que l’opération O (logN) soit fondamentalement de 0,5 seconde * log (N). Eh bien, à ce stade, je voudrais vraiment vous dessiner un graphique avec une flèche à l’intersection de la courbe et de la ligne, en disant: “C’est important ici.” Vous voulez utiliser le log (N) op pour les petits jeux de données et le O (1) op pour les grands jeux de données, dans un tel scénario.

La notation Big-O et l’optimisation des performances constituent un exercice académique plutôt que de fournir une réelle valeur ajoutée aux utilisateurs pour des opérations déjà peu coûteuses, mais s’il s’agit d’une opération coûteuse sur un chemin critique, alors vous êtes certain que cela compte!

Pour tout algorithme pouvant prendre des entrées de différentes tailles N, le nombre d’opérations qu’il prend est limité par une fonction f (N).

Tout Big-O vous dit que c’est la forme de cette fonction.

  • O (1) signifie qu’il y a un nombre A tel que f (N)

  • O (N) signifie qu’il y a un A tel que f (N)

  • O (N ^ 2) signifie qu’il y a un A tel que f (N)

  • O (log (N)) signifie qu’il y a un A tel que f (N)

Big-O ne dit rien à propos de la taille de A (c.-à-d. La vitesse de l’algorithme) ou du croisement de ces fonctions. Cela dit seulement que si vous comparez deux algorithmes, si leurs big-Os diffèrent, alors il y a une valeur de N (qui peut être petite ou très grande) où un algorithme commencera à surpasser l’autre.

vous avez raison, dans de nombreux cas, cela n’a pas d’importance pour des raisons pratiques. mais la question clé est “à quelle vitesse GROWS N”. la plupart des algorithmes que nous connaissons prennent la taille de l’entrée, donc elle croît linéairement.

mais certains algorithmes ont la valeur de N dérivée de manière complexe. si N est “le nombre de combinaisons de loteries possibles pour une loterie avec X numéros distincts”, cela a de l’importance si votre algorithme est O (1) ou O (logN)

Big-OH ​​vous dit qu’un algorithme est plus rapide qu’un autre étant donné un facteur constant. Si votre saisie implique un facteur constant suffisamment petit, vous pourriez obtenir de meilleurs résultats en effectuant une recherche linéaire plutôt qu’une recherche log (n) sur une base.

O (log N) peut être trompeur. Prenons par exemple les opérations sur les arbres rouge-noir .
Les opérations sont O (logN) mais plutôt complexes, ce qui signifie de nombreuses opérations de bas niveau.

Je ne crois pas aux algorithmes où vous pouvez choisir librement entre O (1) avec une grande constante et O (logN) existe vraiment. S’il y a N éléments avec lesquels travailler au début, il est tout simplement impossible de le rendre O (1), la seule chose possible est de déplacer votre N vers une autre partie de votre code.

Ce que j’essaie de dire, c’est que dans tous les cas réels, je sais que vous avez un compromis espace / temps, ou un prétraitement tel que la compilation de données à une forme plus efficace.

C’est-à-dire que vous n’allez pas vraiment en O (1), vous déplacez simplement la partie N ailleurs. Soit vous échangez les performances d’une partie de votre code avec une quantité de mémoire, soit vous échangez les performances d’une partie de votre algorithme avec une autre. Pour restr sain d’esprit, vous devriez toujours regarder l’image plus grande.

Mon point est que si vous avez N éléments, ils ne peuvent pas disparaître. En d’autres termes, vous pouvez choisir entre des algorithmes O (n ^ 2) inefficaces ou pire et O (n.logN): c’est un choix réel. Mais tu ne vas jamais vraiment O (1).

Ce que j’essaie de souligner, c’est que pour chaque problème et état initial des données, il existe un «meilleur» algorithme. Vous pouvez faire pire mais jamais mieux. Avec une certaine expérience, vous pouvez avoir une bonne idée de ce qu’est cette complexité insortingsique. Alors, si votre traitement global correspond à cette complexité, vous savez que vous avez quelque chose. Vous ne pourrez pas réduire cette complexité, mais seulement la déplacer.

Si le problème est O (n), il ne deviendra pas O (logN) ou O (1), vous appendez simplement un prétraitement tel que la complexité globale rest inchangée ou pire et qu’une étape ultérieure sera potentiellement améliorée. Disons que vous voulez le plus petit élément d’un tableau, vous pouvez rechercher dans O (N) ou sortinger le tableau en utilisant n’importe quel traitement de sorting commun O (NLogN), puis utiliser le premier avec O (1).

Est-ce une bonne idée de le faire avec désinvolture? Seulement si votre problème a également demandé des éléments deuxième, troisième, etc. Alors votre problème initial était vraiment O (NLogN), pas O (N).

Et ce n’est pas la même chose si vous attendez dix ou vingt fois plus longtemps pour votre résultat car vous avez simplifié en disant O (1) = O (LogN).

J’attends un contre-exemple 😉 c’est un cas réel où vous avez le choix entre O (1) et O (LogN) et où chaque étape O (LogN) ne se comparera pas à O (1). Tout ce que vous pouvez faire est de prendre un algorithme plus mauvais au lieu d’un algorithme naturel ou de déplacer un traitement lourd vers une autre partie des images plus grandes (résultats de pré-calcul, utilisation d’espace de stockage, etc.).

Disons que vous utilisez un algorithme de traitement d’image qui s’exécute dans O (log N), où N est le nombre d’images. Maintenant, le fait de dire que le temps de fonctionnement est constant ferait croire que peu importe le nombre d’images, la tâche se terminerait à peu près dans le même temps. Si l’exécution de l’algorithme sur une seule image prend une journée entière, en supposant que O (logN) ne sera jamais supérieur à 100, imaginez la surprise de cette personne qui tenterait d’exécuter l’algorithme sur une très grande firebase database d’images. – il s’attendrait à ce que cela se fasse dans un jour ou deux … mais ça prendra des mois pour que ça se termine.