Quoi de neuf avec O (1)?

J’ai remarqué une utilisation très étrange de O (1) dans la discussion d’algorithmes impliquant le hachage et les types de recherche, souvent dans le cadre de l’utilisation d’un type de dictionnaire fourni par le système linguistique ou de types dictionnaire ou tableau de hachage utilisés avec array -index notation.

Fondamentalement, O (1) signifie borné par un temps constant et (typiquement) un espace fixe. Certaines opérations assez fondamentales sont O (1), bien que l’utilisation de langages intermédiaires et de machines virtuelles spéciales entraîne une distorsion (par exemple, comment amortir le garbage collector et les autres processus dynamics sur ce qui serait autrement des activités O).

Mais en ignorant l’amortissement des temps de latence, le ramassage des ordures, etc., je ne comprends toujours pas comment l’hypothèse selon laquelle certaines techniques impliquant une recherche quelconque peuvent être O (1) sauf dans des conditions très particulières.

Bien que je l’ aie déjà remarqué, un exemple vient de apparaître dans la question Pandincus, “Collection ‘appropriée’ à utiliser pour obtenir des éléments en O (1) dans C # .NET?” .

Comme je l’ai remarqué, la seule collection que je connaisse qui offre un access O (1) en tant que limite garantie est un tableau à liaison fixe avec une valeur d’index entière. La présomption est que le tableau est implémenté par un mappage à la mémoire vive qui utilise les opérations O (1) pour localiser la cellule ayant cet index.

Pour les collections qui impliquent une recherche quelconque pour déterminer l’emplacement d’une cellule correspondante pour un type d’index différent (ou pour un tableau fragmenté avec index entier), la vie n’est pas si simple. En particulier, s’il y a des collisions et que la congestion est possible, l’access n’est pas exactement O (1). Et si la collecte est flexible, il faut reconnaître et amortir le coût d’expansion de la structure sous-jacente (comme un arbre ou une table de hachage) pour lequel la congestion (p. Ex. Forte incidence des collisions ou déséquilibre des arbres).

Je n’aurais jamais pensé parler de ces structures flexibles et dynamics comme O (1). Pourtant, je les vois comme des solutions O (1) sans aucune identification des conditions qui doivent être maintenues pour que l’access O (1) soit réellement assuré (et que cette constante soit négligeable).

LA QUESTION: Toute cette préparation est vraiment pour une question. Quelle est la désinvolture autour de O (1) et pourquoi est-il accepté si aveuglément? Est-il reconnu que même O (1) peut être trop grand, même s’il est presque constant? Ou est-ce O (1) simplement l’appropriation d’une notion de complexité de calcul à un usage informel? Je suis perplexe

MISE À JOUR: Les réponses et les commentaires indiquent où je me suis senti désinvolte en définissant moi-même O (1), et je l’ai réparé. Je suis toujours à la recherche de bonnes réponses, et certains des commentaires sont plus intéressants que leurs réponses, dans quelques cas.

Je crois comprendre que O (1) n’est pas nécessairement constant; plutôt, il ne dépend pas des variables considérées. Ainsi, une recherche de hachage peut être considérée comme étant O (1) par rapport au nombre d’éléments dans le hachage, mais pas en ce qui concerne la longueur des données en cours de hachage ou le rapport des éléments aux compartiments dans le hachage.

L’autre élément de confusion est que la grande notation O décrit le comportement limitant. Ainsi, une fonction f (N) pour de petites valeurs de N peut en effet présenter une grande variation, mais vous auriez tout de même raison de dire que c’est O (1) si la limite à l’approche de N est constante par rapport à N.

Le problème est que les gens sont vraiment bâclés avec la terminologie. Il y a 3 classes importantes mais distinctes ici:

O (1) pire cas

C’est simple: toutes les opérations ne prennent pas plus que le temps constant dans le pire des cas, et donc dans tous les cas. L’access à un élément d’un tableau est O(1) pire des cas.

O (1) le pire des cas amorti

Amorti signifie que toutes les opérations ne sont pas O(1) dans le pire des cas, mais pour toute séquence de N opérations, le coût total de la séquence est nul O(N) dans le pire des cas. Cela signifie que même si nous ne pouvons pas limiter le coût d’une opération unique par une constante, il y aura toujours suffisamment d’opérations “rapides” pour compenser les opérations “lentes”, de sorte que la durée d’exécution de la séquence d’opérations soit linéaire dans le nombre d’opérations.

Par exemple, le tableau dynamic standard qui double sa capacité lorsqu’il est rempli nécessite le temps amorti O(1) pour insérer un élément à la fin, même si certaines insertions nécessitent un temps O(N) – il y a toujours suffisamment d’insertions O(1) l’insertion de N éléments prend toujours le total du temps O(N) .

O (1) cas moyen

Celui-ci est le plus délicat. Il existe deux définitions possibles du cas moyen: un pour les algorithmes randomisés à entrées fixes et un pour les algorithmes déterministes à entrées aléatoires.

Pour les algorithmes randomisés avec des entrées fixes, nous pouvons calculer la durée moyenne des cas pour une entrée donnée en analysant l’algorithme et en déterminant la dissortingbution de probabilité de toutes les durées possibles et en prenant la moyenne sur cette dissortingbution (selon l’algorithme). peut ne pas être possible en raison du problème de suspension).

Dans l’autre cas, nous avons besoin d’une dissortingbution de probabilité sur les entrées. Par exemple, si nous devions mesurer un algorithme de sorting, une dissortingbution de probabilité serait la dissortingbution qui a tout N! les permutations possibles de l’entrée sont également probables. Ensuite, la durée de fonctionnement moyenne est la durée moyenne de toutes les entrées possibles, pondérée par la probabilité de chaque entrée.

Puisque le sujet de cette question concerne les tables de hachage, qui sont déterministes, je vais me concentrer sur la deuxième définition du cas moyen. Maintenant, nous ne pouvons pas toujours déterminer la dissortingbution des probabilités des entrées car, bien, nous pourrions avoir à peu près n’importe quoi, et ces éléments pourraient provenir d’un utilisateur les saisissant dans ou à partir d’un système de fichiers. Par conséquent, quand on parle de tables de hachage, la plupart des gens supposent que les entrées sont bien comscopes et que la fonction de hachage se comporte bien, de sorte que la valeur de hachage de toute entrée est dissortingbuée uniformément et aléatoirement.

Prenez un moment et laissez ce dernier point s’enfoncer – la performance moyenne des tables de hachage O(1) provient de l’hypothèse que toutes les valeurs de hachage sont uniformément dissortingbuées. Si cette hypothèse est violée (ce qui n’est généralement pas le cas, mais cela peut certainement arriver et se produit), le temps d’exécution n’est plus en moyenne O(1) .

Voir aussi Déni de service par complexité algorithmique . Dans cet article, les auteurs expliquent comment ils ont exploité certaines faiblesses des fonctions de hachage par défaut utilisées par deux versions de Perl pour générer un grand nombre de chaînes avec des collisions de hachage. Armés de cette liste de chaînes, ils ont généré une attaque par déni de service sur certains serveurs Web en leur fournissant ces chaînes qui entraînaient le pire comportement O(N) dans les tables de hachage utilisées par les serveurs Web.

O (1) signifie temps constant et (typiquement) espace fixe

Juste pour clarifier ce sont deux déclarations distinctes. Vous pouvez avoir O (1) dans le temps mais O (n) dans l’espace ou autre.

Est-il reconnu que même O (1) peut être trop grand, même s’il est presque constant?

O (1) peut être impraticable et il est toujours O (1). Il est souvent négligé que si vous savez que vous disposerez d’un très petit dataset, la constante est plus importante que la complexité, et pour des ensembles de données raisonnablement petits, c’est un équilibre des deux. Un algorithme O (n!) Peut surpasser un O (1) si les constantes et les tailles des ensembles de données sont à l’échelle appropriée.

La notation O () est une mesure de la complexité – pas le temps que prendra un algorithme, ou une mesure pure de la “qualité” d’un algorithme donné pour un objective donné.

Je peux voir ce que vous dites, mais je pense qu’il existe quelques hypothèses de base sous-jacentes à l’affirmation selon laquelle les recherches dans une table de hachage ont une complexité de O (1).

  • La fonction de hachage est raisonnablement conçue pour éviter un grand nombre de collisions.
  • L’ensemble de clés est dissortingbué de manière assez aléatoire, ou du moins pas conçu pour rendre la fonction de hachage médiocre.

La pire des complexités d’une consultation de table de hachage est O (n), mais c’est extrêmement improbable compte tenu des 2 hypothèses ci-dessus.

Hashtables est une structure de données qui prend en charge la recherche et l’insertion O (1).

Une table de hachage a généralement une paire clé / valeur, la clé étant utilisée comme paramètre d’une fonction (une fonction de hachage ) qui déterminera l’emplacement de la valeur dans sa structure de données interne , généralement un tableau.

Comme l’insertion et la recherche ne dépendent que du résultat de la fonction de hachage et non de la taille de la table de hachage ni du nombre d’éléments stockés, une table de hachage possède une insertion et une recherche O (1).

Il y a cependant une mise en garde . Autrement dit, à mesure que la table de hachage devient de plus en plus pleine, il y aura des collisions de hachage où la fonction de hachage renverra un élément d’un tableau déjà occupé. Cela nécessitera une résolution de collision afin de trouver un autre élément vide.

Lorsqu’une collision de hachage se produit, une recherche ou une insertion ne peut pas être effectuée en heure O (1). Cependant, de bons algorithmes de résolution de collision peuvent réduire le nombre d’essais pour trouver un autre emplacement vide approprié ou augmenter la taille de la table de hachage peut réduire le nombre de collisions en premier lieu.

Donc, en théorie, seule une table de hachage soutenue par un tableau avec un nombre infini d’éléments et une fonction de hachage parfaite serait capable d’atteindre les performances O (1) , car c’est le seul moyen d’éviter les collisions de hachage qui augmentent le nombre de opérations requirejses. Par conséquent, tout tableau de taille finie sera à un moment ou un autre inférieur à O (1) en raison de collisions de hachage.


Regardons un exemple. Utilisons une table de hachage pour stocker les paires suivantes (key, value) :

  • (Name, Bob)
  • (Occupation, Student)
  • (Location, Earth)

Nous allons implémenter le backend hashtable avec un tableau de 100 éléments.

La key sera utilisée pour déterminer un élément du tableau pour stocker la paire ( key , value ). Afin de déterminer l’élément, la fonction hash_function sera utilisée:

  • hash_function("Name") renvoie 18
  • hash_function("Occupation") renvoie 32
  • hash_function("Location") renvoie 74 .

À partir du résultat ci-dessus, nous allons assigner les paires (key, value) aux éléments du tableau.

 array[18] = ("Name", "Bob") array[32] = ("Occupation", "Student") array[74] = ("Location", "Earth") 

L’insertion ne nécessite que l’utilisation d’une fonction de hachage et ne dépend pas de la taille de la table de hachage ni de ses éléments, elle peut donc être effectuée en heure O (1).

De même, la recherche d’un élément utilise la fonction de hachage.

Si nous voulons rechercher la clé "Name" , nous allons effectuer une fonction de hash_function("Name") pour savoir quel élément du tableau la valeur souhaitée réside.

En outre, la recherche ne dépend pas de la taille de la table de hachage ni du nombre d’éléments stockés, donc d’une opération O (1).

Tout est bien. Essayons d’append une entrée supplémentaire de ("Pet", "Dog") . Cependant, il y a un problème, car hash_function("Pet") renvoie 18 , qui est le même hachage pour la clé "Name" .

Par conséquent, nous devrons résoudre cette collision de hachage. Supposons que la fonction de résolution de collision par hachage que nous avons utilisée ait trouvé que le nouvel élément vide est 29 :

 array[29] = ("Pet", "Dog") 

Comme il y avait une collision de hachage dans cette insertion, notre performance n’était pas tout à fait O (1).

Ce problème surgira également lorsque nous essayons de rechercher la clé "Pet" , car essayer de trouver l’élément contenant la clé "Pet" en exécutant hash_function("Pet") renverra toujours 18 initialement.

Une fois que nous avons recherché l’élément 18, nous trouvons la clé "Name" plutôt que "Pet" . Lorsque nous trouvons cette incohérence, nous devons résoudre la collision afin de récupérer l’élément correct qui contient la clé "Pet" réelle. Résoudre une collision de hachage est une opération supplémentaire qui empêche la table de hachage de fonctionner à l’heure O (1).

Je ne peux pas parler des autres discussions que vous avez vues, mais il existe au moins un algorithme de hachage garanti pour O (1).

Le hachage de coucou maintient un invariant pour qu’il n’y ait pas de chaînage dans la table de hachage. L’insertion est amortie O (1), la récupération est toujours O (1). Je n’ai jamais vu d’implémentation, c’est quelque chose qui a été découvert récemment quand j’étais au collège. Pour les ensembles de données relativement statiques, cela devrait être un très bon O (1), car il calcule deux fonctions de hachage, effectue deux recherches et connaît immédiatement la réponse.

Cela dit, cela suppose que le calcul du hachage est également O (1). Vous pourriez argumenter que pour les chaînes de longueur K, tout hachage est au minimum O (K). En réalité, vous pouvez relier K assez facilement, par exemple K <1000. O (K) ~ = O (1) pour K <1000.

Il y a peut-être une erreur conceptuelle sur la façon dont vous comprenez la notation Big-Oh. Cela signifie que, étant donné un algorithme et un dataset d’entrée, la limite supérieure du temps d’exécution de l’algorithme dépend de la valeur de la fonction O lorsque la taille de l’dataset tend vers l’infini.

Quand on dit qu’un algorithme prend O (n) le temps, cela signifie que le temps d’exécution pour le pire cas d’un algorithme dépend linéairement de la taille du jeu d’entrées.

Lorsqu’un algorithme prend O (1) le temps, la seule chose que cela signifie est que, étant donné une fonction T (f) qui calcule le temps d’exécution d’une fonction f (n), il existe un nombre positif naturel k tel que T (f)

Maintenant, cela ne signifie en aucun cas que la limite est petite, mais simplement qu’elle est indépendante de la taille du jeu d’entrées. Donc, si je définis artificiellement une borne k pour la taille d’un dataset, sa complexité sera alors O (k) == O (1).

Par exemple, la recherche d’une instance d’une valeur sur une liste chaînée est une opération O (n). Mais si je dis qu’une liste a au plus 8 éléments, alors O (n) devient O (8) devient O (1).

Dans ce cas, nous avons utilisé une structure de données sortinge comme dictionnaire (une arborescence de caractères, où le nœud feuille contient la valeur de la chaîne utilisée comme clé), si la clé est bornée, alors son temps de recherche peut être considéré comme O ( 1) (Si je définis un champ de caractères comme ayant au plus k caractères de longueur, ce qui peut être une hypothèse raisonnable dans de nombreux cas).

Pour une table de hachage, tant que vous supposez que la fonction de hachage est bonne (dissortingbuée aléatoirement) et suffisamment éparse pour minimiser les collisions et que le rehashing est effectué lorsque la structure de données est suffisamment dense, vous pouvez en effet la considérer comme un O (1) ) structure de temps d’access.

En conclusion, le temps O (1) peut être surestimé pour beaucoup de choses. Pour les structures de données volumineuses, la complexité d’une fonction de hachage adéquate peut ne pas être sortingviale et il existe suffisamment de casiers où la quantité de collisions le conduit à se comporter comme une structure de données O, et le rehashing peut devenir excessivement coûteux. Dans ce cas, une structure O (log (n)) telle qu’une AVL ou un B-tree peut être une alternative supérieure.

En général, je pense que les gens les utilisent de manière comparative sans se soucier de leur exactitude. Par exemple, les structures de données basées sur le hachage sont O (1) (moyenne) recherche si elles sont bien conçues et que vous avez un bon hachage. Si tout se passe dans un seul seau, alors c’est O (n). En règle générale, bien que l’on utilise un bon algorithme et que les clés soient dissortingbuées de manière raisonnable, il est pratique d’en parler en tant que O (1) sans toutes les qualifications. De même avec les listes, les arbres, etc. Nous pensons à certaines implémentations et il est tout simplement plus pratique d’en parler lors des discussions sur les généralités, sans les qualifications. Si, par contre, nous discutons d’implémentations spécifiques, alors il est probablement préférable d’être plus précis.

Les recherches de HashTable sont de type O (1) par rapport au nombre d’éléments de la table, car peu importe le nombre d’éléments que vous ajoutez à la liste, le coût de hachage d’un seul élément est sensiblement le même vous l’adresse de l’article.


Pour répondre à cette question, le PO s’est interrogé sur les raisons pour lesquelles O (1) semblait être utilisé de manière si déconcertante alors que, de son sharepoint vue, cela ne pouvait évidemment pas s’appliquer dans de nombreuses circonstances. Cette réponse explique que le temps O (1) est vraiment possible dans ces circonstances.

O (1) signifie exactement que la complexité temporelle de l’algorithme est limitée par une valeur fixe. Cela ne signifie pas qu’il est constant, mais qu’il est limité indépendamment des valeurs d’entrée. Ssortingctement parlant, de nombreux algorithmes temporels supposés O (1) ne sont pas réellement O (1) et vont tellement lentement qu’ils sont bornés pour toutes les valeurs d’entrée pratiques.

Oui, la récupération de la mémoire affecte la complexité asymptotique des algorithmes exécutés dans l’arène collectée. Ce n’est pas sans frais, mais il est très difficile à parsingr sans méthodes empiriques, car les coûts d’interaction ne sont pas compositionnels.

Le temps passé à collecter les ordures dépend de l’algorithme utilisé. Généralement, les éboueurs modifient les modes à mesure que la mémoire se remplit pour garder ces coûts sous contrôle. Par exemple, une approche courante consiste à utiliser un collecteur de copie de type Cheney lorsque la pression de la mémoire est faible, car le coût est proportionnel à la taille de l’appareil en échange de plus d’espace et à devient plus important, car même si cela rapporte des coûts proportionnels à la configuration en direct pour le marquage et à l’ensemble du tas ou du mort pour le balayage. Au moment où vous ajoutez le marquage de cartes et d’autres optimisations, etc., les coûts les plus bas pour un ramasse-miettes pratique peuvent en fait être un peu moins élevés, en prenant un facteur logarithmique supplémentaire pour certains modèles d’utilisation.

Donc, si vous allouez une grande table de hachage, même si vous y accédez à l’aide des recherches O (1) pendant toute sa durée de vie, si vous le faites dans un environnement de récupération de mémoire, le ramasse-miettes est la taille O (n) et vous paierez ce coût périodiquement pendant la collecte.

La raison pour laquelle nous oublions généralement l’parsing de complexité des algorithmes est que la récupération de la mémoire interagit de manière non sortingviale avec votre algorithme. L’importance d’un coût dépend beaucoup de ce que vous faites dans le même processus, donc l’parsing n’est pas compositionnelle.

En outre, au-delà du problème de la copie par rapport au problème du compactage, de la marque et du balayage, les détails de l’implémentation peuvent avoir un impact considérable sur les complexités qui en résultent:

  1. Les ramasse-miettes incrémentielles qui effectuent le suivi des bits sales, etc. peuvent tout faire disparaître.
  2. Cela dépend si votre GC fonctionne périodiquement en fonction de l’heure de l’horloge murale ou est proportionnel au nombre d’atsortingbutions.
  3. Si un algorithme de style mark et sweep est simultané ou stop-the-world
  4. Si elle marque de nouvelles allocations en noir si elle les laisse blanches jusqu’à ce qu’elles les déposent dans un conteneur noir.
  5. Que votre langage admette des modifications de pointeurs peut permettre à certains éboueurs de travailler en un seul passage.

Enfin, lorsque nous discutons d’un algorithme, nous discutons d’un homme de paille. Les asymptotiques n’intègreront jamais complètement toutes les variables de votre environnement. Il est rare que vous implémentiez chaque détail d’une structure de données comme prévu. Vous empruntez une fonctionnalité ici et là, vous déposez une table de hachage parce que vous avez besoin d’un access rapide non ordonné, vous utilisez une union-find sur des ensembles disjoints avec une compression de chemin et une union par rang pour y fusionner permettre de payer un coût proportionnel à la taille des régions lorsque vous les fusionnez ou ce que vous avez. Ces structures sont considérées comme des primitives et les asymptotiques vous aident à planifier des caractéristiques de performance globales pour la structure «dans son ensemble», mais la connaissance des constantes est également importante.

Vous pouvez implémenter cette table de hachage avec des caractéristiques asymptotiques parfaitement identiques à O (1), mais n’utilisez pas la récupération de mémoire; mappez-le en mémoire à partir d’un fichier et gérez-le vous-même. Vous n’aimerez probablement pas les constantes impliquées cependant.

Les implémentations de tables de hachage ne sont en pratique pas “exactement” O (1) en cours d’utilisation, si vous en testez une, vous trouverez en moyenne environ 1,5 recherche pour trouver une clé donnée dans un grand dataset.

(en raison du fait que des collisions se produisent, et lors d’une collision, un emplacement différent doit être atsortingbué)

En outre, dans la pratique, les HashMaps sont soutenus par des tableaux de taille initiale, qui ont été “agrandis” pour atteindre une taille moyenne de 70%, ce qui donne un espace d’adressage relativement bon. Après 70%, les taux de collision augmentent plus rapidement.

La théorie de Big O stipule que si vous avez un algorithme O (1), ou même un algorithme O (2), le facteur critique est le degré de relation entre la taille du jeu d’entrée et les étapes d’insertion / extraction. O (2) est toujours un temps constant, nous nous en approchons simplement comme O (1), car cela signifie plus ou moins la même chose.

En réalité, il n’y a qu’une seule façon d’avoir une “hashtable parfaite” avec O (1), et cela nécessite:

  1. Un générateur de clé de hachage global parfait
  2. Un espace d’adressage sans limite.

( Cas d’exception : si vous pouvez calculer à l’avance toutes les permutations de clés autorisées pour le système et que votre espace d’adresse de magasin de sauvegarde cible est défini comme la taille de toutes les clés autorisées, vous pouvez avoir un hachage parfait , mais c’est une perfection “domaine limité”)

Étant donné une allocation de mémoire fixe, ce n’est pas plausible, car cela suppose que vous disposez d’un moyen magique d’emballer une quantité infinie de données dans un espace fixe sans perte de données, ce qui est impossible sur le plan logistique. .

Donc, rétrospectivement, obtenir O (1.5) qui est toujours un temps constant, dans une quantité de mémoire finie, même avec un générateur de clé de hachage relativement naïf, je trouve ça vraiment génial.

Suffixory note Remarque J’utilise O (1.5) et O (2) ici. Celles-ci n’existent pas en big-o. Ce ne sont que ce que les gens qui ne connaissent pas le big-o sont la raison d’être.

Si quelque chose nécessite 1,5 pas pour trouver une clé, ou 2 étapes pour trouver cette clé, ou 1 étape pour trouver cette clé, mais le nombre d’étapes ne dépasse jamais 2 et si 1 étape ou 2 est complètement aléatoire, alors Big-of of O (1). En effet, quel que soit le nombre d’éléments à append à la taille du jeu de données, il conserve les <2 étapes. Si pour toutes les tables> 500 clés, il faut 2 étapes, vous pouvez supposer que ces 2 étapes sont en fait en une étape avec 2 parties, ce qui est toujours O (1).

Si vous ne pouvez pas faire cette hypothèse, alors vous ne pensez pas du tout à Big-O, car vous devez alors utiliser le nombre qui représente le nombre d’étapes de calcul fini requirejses pour tout faire et “one-step” n’a pas de sens pour vous. Entrez simplement dans votre tête qu’il n’y a pas de corrélation directe entre Big-O et le nombre de cycles d’exécution impliqués.

Je pense que quand beaucoup de personnes jettent le terme «O (1)», elles ont implicitement en tête une «petite» constante, quel que soit «petit» signifie dans leur contexte.

Vous devez prendre toute cette parsing big-O avec le contexte et le bon sens. Cela peut être un outil extrêmement utile ou ridicule, selon votre utilisation.