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

chaque fois que je considère les 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?

journal(infini) < 100, pour toutes fins pratiques.

je suis vraiment curieux pour des exemples du monde réel où cela ne tient pas.

pour clarifier:

  • je comprends O(f(N))
  • je suis curieux des exemples du monde réel où le asymptotique comportement importe 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 en O( N log N).

cette question Est pour le plaisir (a) de divertissement et (b) de recueillir des arguments à utiliser si je cours (à nouveau) dans une controverse sur la performance d'un design.

45
demandé sur Gavin Miller 2009-09-29 14:40:01

23 réponses

je pense que c'est une approche pragmatique; O(logN) ne sera jamais plus que 64. En pratique, chaque fois que les Termes deviennent aussi "petits" que O(logN), vous devez mesurer pour voir si les facteurs constants s'en sortent. Voir aussi

utilisations de la fonction Ackermann?

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

[Big-Oh] 'Analyse' seulement pour les facteurs qui sont au moins O (N). Pour tout facteur plus petit, grande-oh analyse est inutile, et vous devez mesurer.

et

" avec O (logN) votre taille d'entrée ne question."C'est le point de l'ensemble de question. Bien sûr, c'est important... en théorie . La question que pose L'OP est, importe-t-il dans la pratique ? Je prétendent que la réponse est non, il n'y n'est pas, et ne sera jamais, un ensemble de données pour lequel logN va grandir si vite que pour toujours être battu une constante de temps algorithme. Même pour les plus grandes ensemble de données pratiques imaginables dans le des vies de nos petits-enfants, un logN algorithme a une bonne chance de battre un algorithme de temps constant - vous devez toujours mesure.

EDIT

Un bon discours:

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

environ à mi-chemin, Rich discute hash essais 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 si elle 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 que la plupart des autres réponses à cette question sont tout simplement faux du point de vue du pragmatiste qui veut que son algorithme" tourne vite "et" se balance 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 bon un O(log2(n)) algorithme si ces opérations causent des défauts de page et la lenteur du disque les opérations? Pour la plupart des ensembles de données pertinents an O (n) ou même an O(n^2) l'algorithme, ce qui évite de page les défauts, va exécuter des cercles autour d'elle.

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

22
répondu Brian 2017-05-23 10:31:33

la notation Big O vous indique comment votre algorithme change avec l'entrée croissante. O(1) vous dit qu'il n'a pas d'importance combien votre entrée augmente, l'algorithme sera toujours aussi vite. O (logn) dit que l'algorithme sera rapide, mais que la croissance de votre entrée prendra un peu plus de temps.

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

Prendre de faire 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 rejoindre n'importe quelle quantité de temps et vous avez encore 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 qui était O(N^2), vous préféreriez faire une opération qui était O(1) à l'intérieur, et non O(logn) à l'intérieur.

rappelez-vous aussi que le Big-O de n'importe quoi peut avoir un overhead constant. Disons que les frais généraux constants sont de 1 million. Avec O(1), la constante overhead 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 d'arbre par exemple. Mais cela pourrait être n'importe quoi incluant des octets dans un fichier.

60
répondu Brian R. Bondy 2010-04-21 13:12:25

c'est une erreur courante - rappelez-vous que la notation Big O ne vous parle pas de la performance absolue d'un algorithme à une valeur donnée, elle vous dit 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 pourquoi un algorithme A ~ O (logN) et un algorithme B ~ O (1) sont différents:

si je lance Une sur une entrée de taille, puis sur une entrée de taille 1000000*a, je peut s'attendre à la deuxième entrée pour prendre log(1 000 000) de fois plus longue que la première entrée

si je lance B sur une entrée de taille, puis sur une entrée de taille 1000000*un, je peux attendre la deuxième entrée pour prendre la même quantité de temps que la première entrée

EDIT : en repensant un peu plus à votre question, je pense qu'il y a de la sagesse à y trouver. Alors que je ne dirais jamais qu'il est correct de dire O (lgN) = = O (1), Il est possibilité qu'un algorithme O(lgN) puisse être utilisé sur un algorithme O(1). Cela renvoie au point sur les performances absolues ci-dessus: juste savoir qu'un algorithme est O(1) et un autre algorithme est O(lgN) est pas assez pour déclarer que vous devez utiliser le O(1) sur le O(lgN), il est certainement possible compte tenu de votre gamme d'entrées possibles un O(lgN) pourrait vous servir le mieux.

20
répondu Falaina 2009-09-29 11:20:15

Vous avez demandé un exemple réel. Je vais vous en donner une. Biologie computationnelle. Un brin d'ADN codé en ASCII est quelque part au niveau des gigaoctets dans l'espace. Une base de données typique comprendra évidemment des milliers de ces éléments.

maintenant, dans le cas d'un algorithme d'indexation/recherche, que log(n) multiple fait une grande différence lorsqu'il est couplé avec des constantes. La raison pourquoi? C'est l'une des applications où la taille de votre entrée est astronomique. De plus, la taille des entrées continuera toujours à augmenter.

Certes, ces types de problèmes sont rares. Il n'y a que tant d'applications de cette taille. Dans ces circonstances, cependant... il fait un monde de différence.

7
répondu San Jacinto 2009-09-29 11:59:31

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

pour clarifier: nous écrivons habituellement f(x) = O(logN) pour signifier"f(x) est O(logN)".

de toute façon, O(1) signifie un nombre constant de mesures/temps (limite supérieure) pour effectuer une action, indépendamment de la taille de l'entrée. Mais pour O(logN) , le nombre de pas/temps croît encore en fonction de la taille de l'entrée (le logarithme de celui-ci), il croît juste très lentement. Pour la plupart des applications du monde réel, vous pouvez être sûr en supposant que ce nombre d'étapes ne dépassera pas 100, mais je parie qu'il y a plusieurs exemples d'ensembles de données assez grands pour marquer votre déclaration à la fois dangereux et vide (traces de paquets, mesures environnementales, et beaucoup plus).

5
répondu Michael Foukarakis 2009-09-29 11:08:24

Pour assez petit N, O(N^N) peut dans la 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 pièces, ou une opération à temps constant.

et si toutes les opérations prennent 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, ça a pris 30minutes, donc quand je l'ai lancé sur un ensemble de données cent fois plus grand devrait toujours prendre 30minutes parce que O(logN) est "le même" que O (1).... eh...quoi?

votre affirmation selon laquelle "je comprends O(f(N))" est clairement fausse.

applications du monde Réel, oh... Je ne sais pas.... Chaque utilisation de O()-notation jamais?

recherche binaire dans la liste triée de 10 millions d'articles par exemple. C'est la raison pour laquelle nous utilisons des tables de hachage quand les données deviennent assez grandes. Si vous pensez que O (logN) est le même que O(1), alors pourquoi Vous avez déjà utilisé un hachage au lieu d'un arbre binaire?

5
répondu Thomas 2009-09-29 11:42:08

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

alors, pensez à ce que vous attendez de N pour être. Si vous avez de bonnes raisons de penser que N<10, vous pouvez utiliser une recherche linéaire au lieu d'un fichier 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 des éléments trouvés à la front peut bien dépasser un arbre équilibré plus compliqué, en fonction de l'application .

d'un autre côté, notez que, même si log N n'est pas susceptible de 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 faire ou casser votre application. Si ce n'est pas assez pour vous, vous verrez fréquemment les facteurs de (log n)^2 ou (logN)^3 dans les algorithmes, donc même si vous pensez que vous pouvez ignorer un facteur de (log N), cela ne veut pas dire que vous pouvez en ignorer d'autres.

enfin, notez que l'algorithme simplex pour la programmation linéaire a une performance du pire des cas de O (2^n). Cependant, pour les 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 de temps polynomial pour la programmation linéaire, mais il n'était pas initialement pratique parce que le résultat était trop lent .

de nos jours, il existe des algorithmes alternatifs pratiques pour la programmation linéaire (avec un wost-case temps polynomial, pour ce que cela vaut), qui peuvent dépasser la méthode simplex dans la pratique. Mais, selon le problème, la méthode du simplexe est encore compétitif.

5
répondu comingstorm 2009-09-29 18:24:04

l'observation que O(log n) est souvent impossible à distinguer de O(1) est bonne.

Comme un exemple familier, supposons que nous voulions trouver un seul élément dans un tableau trié d'une 1,000,000,000,000 éléments:

  • avec recherche linéaire, la recherche prend en moyenne 500,000,000 pas
  • avec la recherche binaire, la recherche prend en moyenne 40 Pas

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

  • avec recherche linéaire, la recherche prend en moyenne 500 000 000 001 pas (Changement Impossible à distinguer)
  • avec la recherche binaire, la recherche prend en moyenne 40 étapes (changement Impossible à distinguer)

supposons que nous doublions le nombre d'éléments dans le tableau que nous cherchons, et maintenant nous devons chercher pour un autre élément:

  • avec recherche linéaire, la recherche prend en moyenne 1.000.000.000 pas (Changement extraordinairement perceptible)
  • avec la recherche binaire, la recherche prend en moyenne 41 étapes (changement Impossible à distinguer)

comme nous pouvons le voir dans cet exemple, à toutes fins pratiques, un algorithme O(log n) comme la recherche binaire est souvent impossible à distinguer d'un algorithme O(1) comme l'omniscience.

* Nous utilisons des algorithmes O(log n) parce qu'ils sont souvent impossibles à distinguer du temps constant, et parce qu'ils donnent souvent de meilleurs résultats que les algorithmes de temps linéaire.

évidemment, ces exemples supposent des constantes raisonnables. Il s'agit évidemment d'observations générales qui ne s'appliquent pas à tous les cas. De toute évidence, ces points s'appliquent à l'extrémité asymptotique de la courbe, et non à l'extrémité n=3 .

mais cette observation explique pourquoi, par exemple, nous utilisons des techniques telles que le réglage d'une requête pour faire une recherche d'index plutôt qu'un balayage de table - parce qu'une recherche d'index fonctionne en temps presque constant quelle que soit la taille de l'ensemble de données, tandis qu'un balayage de table est incroyablement lent sur des ensembles de données suffisamment grands. Index seek est O(log n) .

4
répondu yfeldblum 2009-10-03 22:39:00

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

3
répondu sdcvvc 2009-09-29 19:08:17

Qu'entendez-vous par "matière"?

si vous êtes confronté au choix d'un algorithme O(1) et d'un algorithme O(lg n) , alors vous ne devriez pas supposer qu'ils sont égaux. Vous devez choisir la constante de temps. Pourquoi pas vous?

et s'il n'existe pas d'algorithme à temps constant, alors l'algorithme à temps logarithmique est généralement le meilleur que vous pouvez obtenir. Encore une fois, est-ce que importe ? Vous avez juste à prendre le plus rapide que vous pouvez trouver.

pouvez-vous me donner une situation où vous gagneriez quelque chose en définissant les deux comme égaux? Au mieux, ça ne ferait pas de différence, et au pire, tu cacherais de vraies caractéristiques d'évolutivité. Parce que habituellement, un algorithme à temps constant sera plus rapide qu'un algorithme logarithmique.

même si, comme vous le dites, lg(n) < 100 à toutes fins pratiques, c'est quand même un facteur 100 en plus de vos autres frais généraux. Si je l'appelle votre fonction, N fois, alors il commence à compter si votre fonction exécute le temps logarithmique ou constante, parce que la complexité totale est alors O(n lg n) ou O(n) .

donc plutôt que de se demander si" il importe "que vous preniez pour acquis que la complexité logarithmique est constante dans" le monde réel", je demanderais s'il y a un sens à le faire.

souvent, vous pouvez supposer que les algorithmes logarithmiques sont assez rapide , mais que faites-vous gagner en les considérant constants?

2
répondu jalf 2009-09-29 11:01:22

O(logN)*O(logN)*O (logN) est très différent. O(1) * O(1) * O(1) est toujours constant. Aussi un simple quicksort-style O(nlogn) est différent de O(N O(1))=O (n). Essayez de trier 1000 et 1000000 éléments. Ce dernier n'est pas 1000 fois plus lent, c'est 2000 fois, parce que log (n^2)=2log (n)

2
répondu user181060 2009-09-29 11:03:19

le titre de la question est trompeur (bien choisi pour susciter le débat, pensez-vous).

O(log N) == O (1) est évidemment erroné (et l'affiche en est consciente). La notation Big O, par définition, concerne l'analyse asymptotique. Quand vous voyez O (N), N est pris pour approcher l'infini. Si N se voit attribuer une constante, ce n'est pas grand O.

Note, Ce n'est pas juste un détail compliqué que seuls les informaticiens théoriques ont besoin de se soucier. Tous les l'arithmétique utilisée pour déterminer la O fonction d'un algorithme s'appuie sur elle. Lorsque vous publiez la fonction O pour votre algorithme, vous pourriez omettre un lot d'informations sur ses performances.

analyse Big O est cool, parce qu'il vous permet de comparer des algorithmes sans s'enliser dans des questions spécifiques à la plate-forme (tailles de mots, instructions par opération, vitesse de la mémoire par rapport à la vitesse du disque). Quand N VA à l'infini, ces problèmes disparaissent. Mais quand N est 10000, 1000, 100, ces problèmes, avec toutes les autres constantes que nous avons laissées en dehors de la fonction O, commencent à compter.

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 pas bien meilleurs que les algorithmes avec O (log N), selon la taille de l'entrée, et toutes les constantes internes qui ont été omises lors de L'analyse de Big O.

si vous savez que vous allez être en haut N, puis utiliser L'analyse de Big O. Si vous ne l'êtes pas, vous aurez besoin de tests empiriques.

2
répondu Scott A Miller 2009-09-29 15:03:07

en théorie

Oui, dans les 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 est toujours jeter l'information, ce qui rend la limite supérieure sur les opérations que vous avez calculé plus lâche et moins utile. Le remplacement D'un O (log(n)) Par Un O(1) dans votre analyse pourrait entraîner une performance de votre grand n 100 fois pire que ce que vous attendiez d'après votre petit n cas. Votre analyse théorique aurait pu être plus précise et prévoir un problème avant de construire le système.

je dirais que le but pratique de big-O de l'analyse est d'essayer de prédire le temps d'exécution de votre algorithme le plus tôt possible. Vous pouvez faciliter votre analyse en supprimant les Termes log(n), mais vous avez alors réduit la puissance prédictive de l'estimation.

dans la pratique

si vous lisez les papiers originaux de Larry Page et Sergey Brin sur L'architecture de Google, ils parlent d'utiliser des tables de hachage pour tout pour s'assurer que par exemple la recherche d'une page Web mise en cache ne prend qu'une seule recherche sur disque dur. Si vous avez utilisé les indices de l'arbre B pour rechercher, vous pourriez avoir besoin de quatre ou cinq recherches sur disque dur pour faire une recherche non cache [*]. Quadrupler vos besoins de disque sur votre stockage de page Web en cache vaut la peine d'être pris en compte d'un point de vue commercial, et prévisible si vous ne rejetez pas tous les Termes O(log(n)).

P.S. Désolé D'utiliser Google comme exemple, ils sont comme Hitler dans la version informatique de loi de Godwin .

[ * ] en supposant que 4KB lit à partir du disque, 100 milliards de pages web dans l'index, ~ 16 octets par clé dans un noeud d'arbre B.

2
répondu Alex 2009-09-29 15:54:31

comme d'autres l'ont souligné, Big-O vous raconte comment la performance de vos échelles de problème. Faites-moi confiance - il des questions. J'ai rencontré à plusieurs reprises des algorithmes qui étaient tout simplement terribles et n'ont pas réussi à répondre aux demandes des clients parce qu'ils étaient trop lents. Comprendre la différence et trouver une solution O(1) est souvent une énorme amélioration.

Cependant, bien sûr, ce n'est pas toute l'histoire - par exemple, vous remarquerez peut-être que quicksort algorithmes va toujours passer au tri d'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 pour comprendre ce qu'il faut utiliser, et comment ajuster les constantes impliquées.

personne ne dit que O(1) est toujours meilleur que O(log n). Cependant, je peux garantissez-vous qu'un algorithme O(1) aura aussi une meilleure échelle, donc même si vous faites des suppositions incorrectes sur le nombre d'utilisateurs qui seront sur le système, ou la taille des données à traiter, cela n'aura pas d'importance pour l'algorithme.

1
répondu Vitali 2009-09-29 11:45:08

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

par exemple, cela peut mener à de graves erreurs dans l'estimation du rendement de votre programme. Si O (N) programme traité tableau de 1000 éléments en 1 ms, alors vous êtes sûr qu'il va traiter 10 6 éléments en 1 seconde (ou ainsi). Si, cependant, le programme est O(N*logN), alors il lui faudra ~2 secondes pour traiter 10 6 éléments. Cette différence peut être cruciale - par exemple, vous pouvez penser que vous avez assez de puissance de serveur parce que vous recevez 3000 requêtes par heure et vous pensez que votre serveur peut gérer jusqu'à 3600.

autre exemple. Imaginez que vous ayez la fonction f () fonctionnant dans O (logN), et sur chaque itération appelant la fonction g (), qui fonctionne aussi dans O (logN). Alors, si vous remplacez les deux journaux par des constantes, vous pensez que votre programme fonctionne en temps constant. La réalité sera cruelle cependant - deux rondins peuvent vous donner jusqu'à 100*100 multiplicateur.

1
répondu Olexiy 2009-09-29 12:08:28

les règles pour déterminer la notation Big-O sont plus simples quand vous ne décidez pas que O(log n) = O(1).

comme l'a dit krzysio, vous pouvez accumuler des O (log n) S Et alors ils feraient une différence très perceptible. Imaginez que vous faites une recherche binaire: o(log n) comparaisons, puis imaginez que 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 d'une manière ou d'une autre à O (log 10 n) et puis vous remarquerez une grande différence pour ne pas trop grand "n".

1
répondu yairchu 2009-09-29 14:28:18

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

supposons qu'en temps réel l'opération O(1) prenne une seconde sur votre architecture, et l'opération O (logN) est essentiellement .5 secondes * log (N). Eh bien, à ce stade, j'aimerais vraiment vous dessiner un graphique avec une flèche à l'intersection de la courbe et de la ligne, disant, "Il importe ici."Vous voulez utiliser le log (N) op pour les petites (1) op pour les grands ensembles de données, dans un tel scénario.

la notation Big-O et l'optimisation de la performance est un exercice académique plutôt que de fournir une valeur réelle à l'utilisateur pour des opérations qui sont déjà bon marché, mais si c'est une opération coûteuse sur un chemin critique, alors vous pariez que c'est important!

1
répondu Chris Moschini 2009-09-29 16:10:37

pour n'importe quel algorithme qui peut prendre des entrées de différentes tailles N, le nombre d'opérations qu'il prend est limité par une certaine fonction f(N).

tout ce que big-O vous dit est la forme de cette fonction.

  • O(1) signifie qu'il y a un nombre A tel que f (N) < A pour grand N.

  • O(N) signifie qu'il existe Un tel que f(N) < pour UN grand N.

  • O (N^2) signifie qu'il y en a un tel que f (N) < an^2 pour grand N.

  • O(log(N)) signifie qu'il existe Un tel que f(N) < AlogN pour les grandes N.

Big-O ne dit rien sur la taille de A (i.e. la vitesse à laquelle l'algorithme est), ou où ces fonctions se croisent. Il dit seulement que lorsque vous comparez deux algorithmes, si leur grand-Os diffèrent, alors il ya une valeur de N (qui peut être petit ou il peut être très grand) où un algorithme commencera à dépasser l'autre.

1
répondu Mike Dunlavey 2009-09-29 18:27:45

vous avez raison, dans de nombreux cas, il n'a pas d'importance pour pracitcal fins. mais la question clé est "à quelle vitesse croît N". la plupart des algorithmes que nous connaissons prennent la taille de l'entrée, donc il se développe linéairement.

mais certains algorithmes ont la valeur de N dérivée d'une manière complexe. si N est "le nombre de loterie combinaisons pour une loterie avec X numéros distincts" il soudain si votre algorithme est O(1) O(logN)

1
répondu Andreas Petersson 2009-10-05 00:35:19

Big-OH vous dit qu'un algorithme est plus rapide qu'un autre étant donné un facteur constant. Si votre entrée implique un facteur constant suffisamment petit, vous pourriez voir de grands gains de performance en allant avec une recherche linéaire plutôt qu'une recherche log(n) d'une certaine base.

1
répondu CLF 2011-03-02 01:00:08

O (log N) peut être trompeur. Prenez par exemple les opérations sur arbres rouges-noirs .

Les opérations sont O (logN) mais plutôt complexe, ce qui signifie de nombreuses opérations de bas niveau.

0
répondu Nick Dandoulakis 2009-09-29 10:52:46

Je ne crois pas que les algorithmes où vous pouvez librement choisir 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 faire O(1), la seule chose qui est 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 compiler les données à une forme plus efficace.

Qui est, vous n'avez pas vraiment aller en O(1), il suffit de déplacer la N de la partie ailleurs. Soit vous échangez les performances d'une partie de votre code avec une certaine quantité de mémoire, soit vous échangez les performances d'une partie de votre algorithme avec une autre. Pour rester sain d'esprit, vous devriez toujours regarder l'image plus grande.

mon point est que si vous avez N articles, ils ne peuvent pas disparaître. En d'autres termes, vous pouvez choisir entre l'inefficacité de O(n^2) algorithmes ou pire et O(N. logN): c'est un vrai choix. Mais vous n'avez jamais vraiment aller en O(1).

ce que j'essaie de souligner, c'est que pour chaque problème et état initial des données, il y a un "meilleur" algorithme. Vous pouvez faire pire mais jamais mieux. Avec un peu d'expérience, vous pouvez avoir une bonne estimation de ce qui est-ce propre complexité. 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 allez simplement ajouter un certain pré-traitement de sorte que la complexité globale est inchangée ou pire, et potentiellement une étape ultérieure sera améliorée. Si vous voulez le plus petit élément d'un tableau, vous pouvez rechercher dans O(N) ou trier le tableau en utilisant n'importe quel traitement de tri commun O(NLogN) puis avoir le premier en utilisant O(1).

est-ce une bonne idée de faire ça par hasard ? Seulement si votre problème a demandé aussi pour deuxième, troisième, etc. élément. 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 votre résultat parce que vous avez simplifié en disant O(1) = O(LogN).

j'attends un contre-exemple ;-) c'est tout cas réel où vous avez le choix entre O(1) et O(LogN) et où chaque pas O(LogN) ne se comparera pas à L'O(1). Tout ce que vous pouvez faire est de prendre un pire algorithme au lieu de celui naturel ou déplacer certains traitement lourd d'une autre partie des plus grandes images (résultats du pré-calcul, utilisation de l'espace de stockage, etc.)

-1
répondu kriss 2009-10-01 20:37:19

disons que vous utilisez un algorithme de traitement d'image qui tourne en O(log N), Où N est le nombre d'images. Maintenant... en disant qu'il fonctionne en temps constant on ferait croire que peu importe combien d'images il y a, il remplirait toujours sa tâche il à peu près la même quantité de temps. Si l'exécution de l'algorithme sur une image unique hypothétiquement prendre une journée entière, et en supposant que O(logN) ne sera jamais plus de 100... imaginez la surprise de cette personne qui essaierait de courir le algorithme sur une très grande base de données d'images - il s'attend à ce que ce soit fait dans un jour ou deux... mais ça va prendre des mois pour qu'elle se termine.

-1
répondu luvieere 2009-10-02 09:21:15