Existe-il des cas où vous préférez une plus grande-O complexité temporelle de l'algorithme sur le bas de l'un?
Sont qu'il ya des cas où vous préférez O(log n) temps la complexité de O(1) temps de la complexité? Ou O(n) à O(log n)?
Avez-vous des exemples?
- Je préfère un
O(log n)algorithme à uneO(1)algorithme de comprendre si le premier, mais pas le dernier... - Il y a des tonnes de impossible structures de données O(1) opérations de l'informatique théorique. Un exemple serait de select() sur bitvectors, qui peut être pris en charge en o(n) de l'espace supplémentaire, et O(1) par opération, à l'aide de 5 couches d'indirection. Simple binaire de recherche, combiné avec O(1) rang() s'avère être plus rapide dans la pratique, selon l'auteur de la Succincte Structure de Données de la Bibliothèque
- Bas asymptotique de la complexité n'est pas gage temps d'exécution plus rapide. La recherche de la matrice de multiplication par un exemple concret.
- Aussi...tout algorithme peut être converti à O(1), étant donné un nombre suffisamment important de la lecture de la table 😉
- Pour un exemple concret, SmoothSort a le meilleur des cas
O(n)la performance et le pire des casO(n log n), alors que les QuickSort a le meilleur des casO(n log n)la performance et le pire des casO(n ^ 2)(!). Qui voyez-vous en pratique? - C'est en supposant que la table de recherche est O(1), ce qui n'est pas donné à tous pour la taille de vos tables, vous voulez parler! 🙂
- il sera en O(1), parce qu'elle sera indépendante de la saisie. Il va donc dépendre de la taille de l'espace d'entrée (c'est à dire le domaine de la fonction)
- Je vais prendre un algorithme je peux juste appeler à partir de la langue de la bibliothèque sur quoi que ce soit de l'auto-mise en œuvre ou d'un tiers à tout moment, à moins qu'il soit un rendement réel problème dans mon application. Plus vite écrit, plus facile documenté, facile maintenu, mieux testé.
- La différence entre O(1) et O(log n) est seulement de l'intérêt à la théorie de l'ordinateur scientifiques. Les personnes travaillant dans le Monde Réel ont de meilleures choses à s'inquiéter, comme la différence entre O(n) et O(n^2).
- Si l'espace d'entrée est délimitée puis chaque algorithme est de $O(1)$. La complexité n'a d'intérêt que lorsque l'entrée de l'espace n'est pas borné, dans ce cas, votre table de recherche est certainement pas $O(1)$. Par exemple, toute la table de recherche sur un mot-taille architecture est $\Omega(\log(n))$, ce qui est clair, parce que toute la ramification programme avec un maximum de sortance égale à la taille de mot doit être logarithmique en le nombre de sorties.
- Umm. Dire que nous avons tout type de graphe d'algorithme qui dépend de tous les nœuds de décider de la solution. La seule façon de regarder le résultat dans votre table de recherche est de visiter chaque nœud d'entrée au moins une fois (sinon, comment savez-vous quelle solution choisir?). Donc vous avez une complexité au moins O(V). Maintenant, évidemment, si votre taille est limitée, S(V) est une constante qui est en O(1), mais la même chose est vrai pour absolument chaque algorithme et vous n'avez pas besoin de tout type de table de recherche pour que,
- Vraiment le droit. Après réflexion, ce que j'ai dit n'est vrai que dans certains algorithmes, où les entrées sont des valeurs scalaires.
- ah mais la taille de votre entiers augmente de façon logarithmique de la taille de saisie 😉
- Big-O analyse généralement ignore les détails de mise en œuvre (mise en cache, la mémoire, etc.) 😉
- N'a rien à voir avec les détails de mise en œuvre. Si votre entrée est un nombre unique, si ce nombre peut être arbitrairement grand, il faut O(log n) bits pour être représenté, qui nécessite O(log n) le temps de lire. Cela est ignoré par de nombreuses analyses pour une bonne raison, mais si vous ne faites pas attention et d'ignorer cela, vous pouvez facilement prouver que vous avez un polynôme solution pour un NP-difficile de l'algorithme. Voir, par exemple, Pseudo-polynomial en temps.
- Ou si un autre exemple est plus facile: L'entrée de notre susmentionnés graphique problème peut facilement être représenté comme un seul nombre (après tout c'est ce que la mémoire de l'ordinateur est fondamentalement) - donc, par le même argument, comme avant, il ne peut pas être en O(1).
- La question est un peu trop large (comme peut être vu à partir de la très vague réponses qui vont comme: la vitesse, l'espace, l'algorithmique longueur, ...). Vous avez peut-être certains plus spécifiques à des domaines d'application dans l'esprit?
- Vous devez disposer d'un tableau dont les clés de la regarder le graphique lui-même. Il faudrait énumérer tous les possibles graphiques, puisque le graphe est une partie de l'entrée. Le seul problème est que si les graphiques qui peuvent être utilisés est un ensemble infini. De façon réaliste, dans la programmation d'ordinateur, nous pouvons faire l'affirmation que le domaine est techniquement fini depuis que l'ordinateur est finie. Donc Hoten est toujours, au moins à partir d'un certain point de vue.
- Dès que vous supposez que le domaine d'entrée est fini, il n'a pas d'importance si vous utilisez une table de recherche ou pas - dans ce cas, tous les algorithmes sont en O(1) par définition! Quicksort, knappsack, voyageur de commerce - tous les O(1) et que, sans aucun tables de recherche impliqués. Et si vous ne supposez pas que le domaine est fini, la table de recherche de ne pas obtenir de la plupart des problèmes jusqu'à O(1) soit (vous pouvez les obtenir à O(n) avec tout de même).
- Votre déclaration au sujet de la lecture de la table n'a pas de sens parce que nous utilisons big-O notation pour afficher le temps d'exécution asymptotique croissance, exécutez pas le temps lui-même. c'est à dire votre expression doit être valable pour n arbitrairement grand.
- Il y a une jolie structure de données appelée la Bloom filter qui permet d'ajouter et de manière probabiliste de vérifier la présence d'un élément en O(1) fois, mais a la possibilité de mal à répondre "présent" lorsque l'élément n'est pas en fait. Les arbres se donner la réponse avec certitude en O(log n).
- Je serais probablement préfèrent un
O(log n)-time / O(1)-spacealgorithme à uneO(1)-time / O(10^(n^999))-spaceun 🙂 - Cette fameuse question est fortement connexe et illustre un cas où la direction de la prévision des effets causé un log n temps de marche (tri d'un tableau) pour être plus rapide que n (boucler sur le tableau), même pour un assez grand n.
- Parmi les tri des réseaux, l'AKS réseau est théoriciens de la " meilleure construction de profondeur O(log n) par rapport à O((log n)**2) pour Doseur de tri et bitonic tri—mais la constante rend totalement impossible. Knuth: "Doseur de la méthode est beaucoup mieux, à moins que n dépasse la capacité de mémoire totale de tous les ordinateurs sur terre!
- Votre question est mathématiquement demander si un log(x) peut être inférieure à une constante ou si x peut être inférieure à log(x) ou une constante. Jetez un oeil à cette intrigue et à vous de me le dire fooplot.com/plot/m3dwiddyny
- Parfois, le ralentissement de l'algorithme peut avoir d'autres propriétés qui sont importants. Par exemple, le tri rapide est généralement plus rapide que mergesort, mais mergesort est intrinsèquement stable tandis que quicksort ne l'est pas; ainsi, si l'ordre des entrées de l'égalité des touches de questions mergesort peut être préférable.
Vous devez vous connecter pour publier un commentaire.
Il ne peut y avoir de nombreuses raisons de préférer un algorithme d'une plus grande complexité temporelle O sur la partie inférieure:
10^5est mieux de la part de big-O le point de vue que1/10^5 * log(n)(O(1)vsO(log(n)), mais pour la plupart raisonnablenla première fonctionnera mieux. Par exemple le meilleur de la complexité de la multiplication de matrice estO(n^2.373)mais la constante est si élevé que personne (à ma connaissance) de calcul des bibliothèques de l'utiliser.O(n*log(n))ouO(n^2)algorithme.O(log log N)temps de la complexité pour trouver un article, mais il y a aussi un arbre binaire qui trouve la même dansO(log n). Même pour un grand nombre den = 10^20la différence est négligeable.O(n^2)et nécessiteO(n^2)de la mémoire. Il pourrait être préférable par rapport àO(n^3)temps etO(1)de l'espace lorsque la n est pas vraiment grand. Le problème, c'est que vous pouvez attendre pendant une longue période, mais très doute, vous pouvez trouver une RAM assez grand pour l'utiliser avec votre algorithmedans certains endroits (de sécurité) d'une complexité peut être une exigence. Personne ne veut avoir un algorithme de hachage qui peut hachage hyper rapide (car alors d'autres personnes peuvent bruteforce-vous un chemin plus rapide)O(n^2), pire que quicksort ou mergesort, mais comme un algorithme en ligne il peut efficacement trier une liste de valeurs telles qu'elles sont reçues (comme une entrée d'utilisateur) où la plupart des autres algorithmes ne peuvent opérer efficacement sur une liste complète des valeurs.Il est toujours caché constante, qui peut être plus faible sur le O(journal n) de l'algorithme. Ainsi, il peut travailler plus rapidement, dans la pratique, pour les données de vie réelle.
Il y a aussi de l'espace préoccupations (par exemple en cours d'exécution sur un grille-pain).
Il y a aussi le temps du développeur préoccupation - O(journal n) peut-être 1000× plus facile à mettre en œuvre et vérifier.
lg nest tellement, tellement, tellement proche dekpour les grandesnque la plupart des opérations ne seraient jamais remarquer la différence.n.log nest effectivement une constante 64 ou plus petit.O(1); la résolution des collisions par l'intermédiaire d'un arbre de recherche binaire seraitO(log n).Je suis surpris que personne n'a mentionné liés à la mémoire des applications encore.
Il peut y avoir un algorithme qui a moins d'opérations à virgule flottante en raison de sa complexité (c'est à dire O(1) < O(journal n)) ou parce que la constante devant la complexité est moindre (c'est à dire 2n2 < 6n2). Peu importe, il peut toujours préférer l'algorithme avec plus de FLOP si le premier FLOP de l'algorithme est plus liées à la mémoire.
Ce que je veux dire par "mémoire", c'est que vous êtes souvent d'accéder à des données qui est constamment hors de la cache. Afin de récupérer ces données, vous devez tirer la mémoire de votre réalité de l'espace mémoire dans votre cache avant que vous puissiez effectuer votre opération. Extraction étape est souvent assez lent, beaucoup plus lent que votre opération elle-même.
Par conséquent, si votre algorithme nécessite plus d'opérations (et pourtant, ces opérations sont effectuées sur les données qui sont déjà dans le cache (et donc pas de corvée nécessaire]), il sera toujours plus performant que votre algorithme avec moins d'opérations (qui doit être effectuée sur des données en cache [et, par conséquent, nécessitent une extraction]) en termes de mur-temps.
O(logn)surO(1). Vous pourriez très facilement imaginer une situation où pour tout votre possiblen, moins liés à la mémoire de l'application permettrait de courir plus rapidement dans le mur-temps, même à une plus grande complexité.Dans des contextes où la sécurité des données est une préoccupation, un algorithme plus complexe peut être préférable à une moins algorithme complexe si l'algorithme plus complexe a une meilleure résistance à le timing des attaques.
(n mod 5) + 1, il est encoreO(1), mais révèle des informations surn. Ainsi, un algorithme plus complexe avec plus lisse d'exécution peut être préférable, même si elle peut être asymptotiquement (et peut-être même dans la pratique) plus lent.Alistra cloué, mais a échoué à fournir des exemples, je vais donc.
Vous avez une liste de 10 000 codes UPC, pour ce que votre magasin vend. Les 10 chiffres du code à barres, entier pour le prix (le prix en pièces d'un cent) et 30 caractères de la description de la réception.
O(log N) approche: Vous avez une liste triée. 44 octets si ASCII, 84 si l'Unicode. Alternativement, le traiter de l'UPC comme un int64 et vous obtenez 42 & 72 octets. 10 000 enregistrements--dans le plus haut le cas où vous êtes à la recherche à un peu moins d'un méga-octet de stockage.
O(1) approche: Ne pas stocker l'UPC, au lieu de l'utiliser comme une entrée dans le tableau. Dans les bas-cas où vous êtes à la recherche à de près d'un tiers d'un téraoctet de stockage.
L'approche que vous utilisez dépend de votre matériel. Sur les plus raisonnables moderne de configuration que vous allez utiliser le journal N approche. Je peux imaginer la deuxième méthode est la bonne réponse si pour une raison quelconque, vous êtes en cours d'exécution dans un environnement où la RAM est extrêmement court, mais vous avez beaucoup de stockage de masse. Un tiers d'un téraoctet sur un disque n'est pas une grosse affaire, de l'obtention de vos données dans une seule sonde du disque vaut quelque chose. La simple approche binaire prend 13 en moyenne. (Notez, cependant, que par le regroupement de vos clés, vous pouvez obtenir une garantie de 3 lectures et, dans la pratique, vous le cache de la première.)
malloc(search_space_size)et subscripting en ce qu'elle renvoie est aussi facile qu'il obtient.Envisager un rouge-l'arbre noir. Il a accès, de recherche, d'insertion et de suppression de
O(log n). Comparer à un tableau, qui a l'accès deO(1)et le reste de la opérations sontO(n).Donc donné une application où nous insérer, supprimer ou rechercher plus souvent que nous l'accès et le choix entre ces deux structures, nous préférons le rouge-l'arbre noir. Dans ce cas, vous pourriez dire que nous préférons le rouge-noir est un arbre de plus en plus lourde
O(log n)temps d'accès.Pourquoi? Parce que l'accès n'est pas notre principale préoccupation. Nous faisons un compromis: les performances de notre application est plus fortement influencée par des facteurs autres que celui-ci. Nous permettre que cet algorithme à souffrir de la performance parce que nous avons fait des gains importants en optimisant d'autres algorithmes.
Donc la réponse à votre question est simple: lorsque l'algorithme du taux de croissance n'est pas ce que nous voulons optimiser les, lorsque l'on veut optimiser autre chose. Toutes les autres réponses sont des cas particuliers de ce. Parfois, nous optimiser le temps d'exécution d'autres opérations. Parfois, nous optimisons pour la mémoire. Parfois, nous optimisons pour la sécurité. Parfois, nous optimisons la maintenabilité. Parfois nous pour optimiser le temps de développement. Même la principale constante étant suffisamment faible pour de la matière est de l'optimisation de l'exécution lorsque vous connaissez le taux de croissance de l'algorithme n'est pas le plus grand impact sur les temps d'exécution. (Si votre ensemble de données était en dehors de cette plage, vous permettrait d'optimiser le taux de croissance de l'algorithme, car il finirait par dominer la constante.) Tout a un coût, et dans de nombreux cas, nous négocions le prix d'un taux de croissance plus élevé pour l'algorithme pour optimiser quelque chose d'autre.
Oui.
Dans un cas réel, nous avons couru quelques tests sur la table des recherches à la fois à court et à long chaîne de clés.
Nous avons utilisé un
std::map, unstd::unordered_mapavec un hachage que les échantillons à plus de 10 fois la longueur de la chaîne (nos clés ont tendance à être guid-like, donc c'est bon), et un hash des échantillons de chaque personnage (dans la théorie de la réduction des collisions), un vecteur trié où nous faisons un==comparer, et (si je me souviens bien) un vecteur trié où nous stockons également une table de hachage, d'abord comparer le hash, puis de comparer les caractères.Ces algorithmes gamme de
O(1)(unordered_map) àO(n)(recherche linéaire).Modeste de taille N, très souvent, le O(n), qui a battu le O(1). Nous soupçonnons que c'est parce que le nœud à base de conteneurs nécessaires à notre ordinateur à sauter partout dans la mémoire de plus, alors que le linéaire basée sur les contenants n'ont pas.
O(lg n)existe entre les deux. Je ne me souviens pas comment il a fait.La différence de performances n'est pas que grand, et sur de plus grands ensembles de données la base de hachage on fait beaucoup mieux. Nous avons donc coincé avec la base de hachage non triées de la carte.
Dans la pratique, pour raisonnable de taille n,
O(lg n)estO(1). Si votre ordinateur n'a de la place pour 4 milliards de dollars d'entrées dans votre tableau, puisO(lg n)est délimitée ci-dessus par32. (lg(2^32)=32) (en informatique, lg est à court de main pour le log de base 2).Dans la pratique, lg(n) algorithmes sont plus lents que O(1) algorithmes non pas à cause du facteur de croissance logarithmique, mais parce que le lg(n) de la portion habituellement signifie qu'il ya un certain niveau de complexité de l'algorithme, et que la complexité ajoute un plus grand facteur constant que tout de la "croissance" de la lg(n) terme.
Cependant, complexe O(1) algorithmes (comme le hachage de la cartographie) peut facilement avoir un similaire ou plus grand facteur constant.
La possibilité d'exécuter un algorithme en parallèle.
Je ne sais pas si il y a un exemple pour les classes
O(log n)etO(1), mais pour certains problèmes, vous choisissez un algorithme avec une plus grande complexité de la classe, lorsque l'algorithme est plus facile à exécuter en parallèle.Certains algorithmes ne peuvent pas être parallélisée mais sont de faible complexité de la classe. Prenons un autre algorithme qui donne le même résultat et peut être parallélisée facilement, mais a une plus grande classe de complexité. Lorsqu'il est exécuté sur une machine, le second algorithme est plus lent, mais lorsqu'il est exécuté sur plusieurs machines, le réel le temps d'exécution devient plus en plus faible alors que le premier algorithme ne peut pas accélérer.
Disons que vous êtes à la mise en œuvre d'une liste noire sur un système embarqué, où les nombres entre 0 et 1 000 000 pourrait être mis à l'index. Qui vous laisse deux options possibles:
L'accès à la bitset aurez la garantie d'un accès constant. En termes de temps, de la complexité, il est optimal. À la fois théorique et pratique, du point de vue (il est O(1), avec une très faible constante de frais généraux).
Encore, vous pourriez préférer la seconde solution. Surtout si vous vous attendez à ce que le nombre de mis sur la liste noire des entiers à être très faible, car il sera plus efficace en terme de mémoire.
Et même si vous n'avez pas à développer un système intégré où la mémoire est rare, je ne peux augmentation de la limite arbitraire de 1 000 000 à 1,000,000,000,000 et le même argument. Puis le bitset nécessiterait environ 125G de la mémoire. Avoir une garantie pour le pire des cas complexitity de O(1) peut ne pas convaincre votre patron de vous fournir un tel serveur puissant.
Ici, je préfère largement une recherche binaire (O(log n)) ou de l'arbre binaire (O(log n)) sur le joint(1) bitset. Et, probablement, à une table de hachage avec son pire des cas, la complexité de O(n) va battre tous d'entre eux dans la pratique.
Ma réponse ici Rapide aléatoire pondéré de sélection à travers toutes les lignes d'une matrice stochastique est un exemple où un algorithme de complexité O(m) est plus rapide que celui avec une complexité O(log(m)), lors de la
mn'est pas trop grand.Personnes ont déjà répondu à votre question exacte, donc, je vais aborder une question légèrement différente que les gens peuvent en fait être pensé à venir ici.
Beaucoup de "O(1) le temps des" algorithmes et structures de données en fait seulement prendre devrait O(1) fois, ce qui signifie que leur moyenne temps d'exécution est O(1), peut-être que sous certaines hypothèses.
Exemples courants: tables de hachage, l'expansion de "tableau liste" (un.k.un. dynamiquement la taille des matrices/vecteurs).
Dans de tels scénarios, vous pouvez préférer utiliser les structures de données et algorithmes dont le temps est la garantie d'être absolument délimitée de manière logarithmique, même si elles peuvent effectuer de pire en moyenne.
Un exemple pourrait donc être un équilibre binaire un arbre de recherche, dont le temps d'exécution est de pire en moyenne, mais de mieux dans le pire des cas.
Une question plus générale est que si il y a des situations où l'on préférerait un
O(f(n))algorithme à uneO(g(n))algorithme, même sig(n) << f(n)commentend vers l'infini. Comme d'autres l'ont déjà mentionné, la réponse est clairement "oui" dans le cas oùf(n) = log(n)etg(n) = 1. Il est parfois oui, même dans le cas quef(n)est polynomiale maisg(n)est exponentielle. Un célèbre exemple est celui de la Algorithme Du Simplexe pour la résolution de problèmes de programmation linéaire. Dans les années 1970, il a été montré pour êtreO(2^n). Ainsi, son pire-cas de comportement est infaisable. Mais, sa moyen comportement est très bon, même pour des problèmes pratiques avec des dizaines de milliers de variables et de contraintes. Dans les années 1980, temps polynomial algorithmes (par exemple un Karmarkar de l'algorithme de points intérieurs) pour la programmation linéaire ont été découverts, mais 30 ans plus tard, l'algorithme du simplexe semble toujours être l'algorithme de choix (à l'exception de certains très gros problèmes). C'est pour la raison évidente que la moyenne des cas, le comportement est souvent plus important que le pire cas, le comportement, mais aussi pour une plus subtile raison que l'algorithme du simplexe est dans un certain sens, plus informatif (par exemple, la sensibilité de l'information est plus facile à extraire).De mettre mes 2 cents:
Parfois une aggravation de la complexité de l'algorithme est sélectionné à la place d'un autre, lorsque l'algorithme s'exécute sur un certain environnement matériel. Supposons que notre algorithme O(1) non-séquentielle accède à chaque élément d'une très grande, tableau de taille fixe pour résoudre notre problème. Ensuite, mettre ce tableau sur un disque dur mécanique, ou une bande magnétique.
Dans ce cas, en O(logn) algorithme (supposons qu'il accède à disque de manière séquentielle), devient de plus en plus favorable.
Il est un bon cas d'utilisation pour l'utilisation d'un O(log(n)) l'algorithme au lieu d'un algorithme O(1) que les nombreuses autres réponses ont ignoré: l'immuabilité. De hachage, les cartes ont O(1) met et obtient, en supposant que la bonne distribution de valeurs de hachage, mais ils exigent mutable état. Immuable de l'arborescence de cartes O(log(n)) met et se, qui est asymptotiquement plus lent. Cependant, l'immuabilité peut être assez précieux pour rattraper le pire rendement et, dans le cas où plusieurs versions de la carte doivent être conservés, l'immuabilité vous permet de vous éviter d'avoir à copier la carte, qui est O(n), et donc peut améliorer performance.
Simplement: Parce que le coefficient - les coûts associés à l'installation, le stockage, et le temps d'exécution de cette étape peut être beaucoup, beaucoup plus large, avec un petit big-O de problème qu'avec un plus grand un seul. Big-O est seulement une mesure des algorithmes évolutivité.
Considérons l'exemple suivant de the Hacker Dictionnaire, en proposant un algorithme de tri en s'appuyant sur la L'Interprétation des Mondes multiples de la Mécanique Quantique:
(Source: http://catb.org/~esr/jargon/html/B/bogo-sort.html)
Avis que le big-O de cet algorithme est
O(n), qui bat tout connu algorithme de tri à jour sur les éléments génériques. Le coefficient linéaire étape est également très faible (puisque c'est seulement une comparaison, pas de swap, qui est fait de façon linéaire). Un algorithme similaire pourrait, en fait, être utilisé pour résoudre n'importe quel problème dans les deux NP et co-NP en temps polynomial, puisque chaque solution possible (ou possible, et la preuve qu'il n'y a pas de solution) peut être généré en utilisant le quantum processus, puis vérifiées en temps polynomial.Cependant, dans la plupart des cas, nous ne voulons pas prendre le risque que Plusieurs Mondes pourrait ne pas être correcte, pour ne pas mentionner que la loi de mise en œuvre de l'étape 2 est toujours "de gauche" comme un exercice pour le lecteur".
À tout moment lorsque n est bornée et la constante de multiplicateur de l'algorithme O(1) est supérieure à la limite sur log(n). Par exemple, stocker des valeurs dans un hashset est O(1), mais peuvent nécessiter un calcul coûteux d'une fonction de hachage. Si les éléments de données peuvent être trivialement par rapport (par rapport à un certain ordre), et à la limite sur n est tel que log n est significativement inférieure à la valeur de hachage de calcul sur un élément, puis les stocker dans un arbre binaire équilibré peut être plus rapide que le stockage dans un hashset.
En temps réel de la situation où vous avez besoin d'un cabinet de limite supérieure vous sélectionnez par exemple un heapsort, par opposition à un Quicksort, parce que heapsort du comportement moyen est aussi son pire-cas de comportement.
Ajoutant à la déjà de bonnes réponses.Un exemple concret serait Hash index vs B-arbre d'index dans la base de données postgres.
Hash index d'une table de hachage de l'indice d'accéder aux données sur le disque alors que btree comme son nom l'indique utilise un Arbre de structure de données.
En Big-O, il s'agit de O(1) vs O(logN).
Hash index sont actuellement déconseillée dans postgres depuis dans une situation réelle, en particulier dans les systèmes de base de données, la réalisation de hachage sans collision est très dur(peut conduire à un O(N) le pire des cas complexes) et de ce fait, il est encore plus difficile de faire les crash-fort (appelé écrire à l'avance de journalisation - WAL dans postgres).
Ce compromis est faite dans cette situation depuis O(logN) est assez bonne pour les index et la mise en œuvre de O(1) est assez difficile et la différence de temps ne serait pas vraiment d'importance.
Quand
nest petit, etO(1)est constamment à la lentement.ou
C'est souvent le cas pour les applications de sécurité que nous voulons à des problèmes de conception dont les algorithmes sont lents sur le but, afin d'éviter que quelqu'un l'obtention d'une réponse à un problème trop rapidement.
Voici quelques exemples sur le dessus de ma tête.
O(2^n)temps oùnest la longueur en bits de la clé (ce est la force brute).Ailleurs dans CS, Tri Rapide est
O(n^2), dans le pire des cas, mais dans le cas général estO(n*log(n)). Pour cette raison, le "Big O" l'analyse n'est pas la seule chose que vous vous souciez lors de l'analyse de l'efficacité d'un algorithme.