Qu'est-ce qu'O(1)?

le problème est que les gens sont vraiment négligents avec la terminologie. Il y a ici trois classes importantes mais distinctes:

O(1) pire cas

c'est simple - toutes les opérations ne prennent pas plus d'un temps constant dans le pire des cas, et donc dans tous les cas. L'accès à un élément d'un tableau est O(1) dans le pire des cas.

O (1) worst-case amorti

amorti signifie que toutes les opérations ne sont pas O(1) dans le pire des cas, mais pour toute séquence D'opérations N, Le coût total de la séquence est no O(N) dans le pire des cas. Cela signifie que même si nous ne pouvons pas lié au coût de l'opération par une constante, il y aura toujours assez "rapide" opérations à faire pour la "lenteur" des opérations telles que le temps d'exécution de la séquence d'opérations est linéaire en le nombre d'opérations.

pour par exemple, la norme Dynamic Array qui double sa capacité quand elle se remplit nécessite O(1) temps amorti pour insérer un élément à la fin, même si certaines insertions exigent O(N) temps - il ya toujours assez O(1) insertions que l'insertion N articles prend toujours O(N) temps total.

O(1) cas moyen

celui-ci est le plus compliqué. Il existe deux définitions possibles de average-case: Un pour les algorithmes aléatoires avec entrées fixes, et un pour les algorithmes déterministes avec entrées aléatoires.

pour les algorithmes aléatoires avec entrées fixes, nous pouvons calculer le temps de fonctionnement du cas moyen pour n'importe quelle entrée donnée en analysant l'algorithme et en déterminant la distribution de probabilité de tous les temps de fonctionnement possibles et en prenant la moyenne sur cette distribution (selon l'algorithme, cela peut être ou ne peut pas être possible en raison de L'arrêt Problème.)

dans l'autre cas, nous avons besoin d'une distribution de probabilité sur les entrées. Par exemple, si nous devions mesurer un algorithme de tri, une telle distribution de probabilité serait la distribution qui a tout N! les permutations possibles de l'entrée tout aussi probable. Ensuite, le temps de fonctionnement moyen est le temps de fonctionnement moyen sur toutes les entrées possibles, pondéré par la probabilité de chaque entrée.

puisque le sujet de cette question Est les tables de hachage, qui sont déterministes, je vais me concentrer sur la deuxième définition de cas moyen. Maintenant, nous ne pouvons pas toujours déterminer la distribution de probabilité des entrées parce que, bien, nous pourrions être hashing à peu près n'importe quoi, et ces éléments pourraient provenir d'un utilisateur les tapant dans ou à partir d'un système de fichiers. Par conséquent, quand on parle de tables de hachage, la plupart des gens supposent juste que les entrées sont bien comportées et la fonction de hachage est bien comportée telle que la valeur de hachage de n'importe quelle entrée est distribution essentiellement aléatoire et uniforme sur toute la gamme des valeurs de hachage possibles.

prendre un moment et laisser ce dernier point s'enfoncer dans - le O(1) la performance moyenne de cas pour les tables de hachage vient de supposer que toutes les valeurs de hachage sont uniformément répartis. Si cette hypothèse est violée (ce qui n'est généralement pas le cas, mais elle peut certainement se produire et se produit effectivement), la durée de fonctionnement n'est plus O(1) en moyenne.

Voir aussi Déni de Service de par la Complexité Algorithmique . Dans cet article, Les auteurs discutent comment ils ont exploité certaines faiblesses dans les 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 de déni de service sur certains serveurs Web en leur donnant ces chaînes qui ont abouti au comportement O(N) dans le pire des cas dans les tables de hachage utilisées par les serveurs web.

O(1) signifie que la constante de temps et (généralement) fixe de l'espace

Juste pour clarifier ces deux états distincts. Vous pouvez avoir O(1) dans le temps mais O(n) dans l'espace ou quoi que ce soit.

est-il reconnu que même O(1) peut être immanquablement grand, même si presque constant?

O(1) peut être impractically ÉNORME et il est toujours en O(1). Il est souvent négligé que si vous savez que vous avoir un très petit ensemble de données la constante est plus importante que la complexité, et pour des ensembles de données raisonnablement petits, c'est un équilibre entre les deux. Un O(N! l'algorithme peut effectuer un O(1) si les constantes et les tailles des ensembles de données de l'échelle appropriée.

O() notation est une mesure de la complexité - pas le temps d'un algorithme, ou une pure mesure de la "bonne" un algorithme donné est pour un but donné.

je peux voir ce que vous dites, mais je pense qu'il y a quelques hypothèses de base qui sous-tendent l'affirmation que 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 des touches est distribué assez au hasard, ou du moins pas conçu expressément pour rendre la fonction de hachage effectuer mal.

Le pire la complexité d'une recherche de table de hachage est O (n), mais cela est extrêmement improbable compte tenu des deux hypothèses ci-dessus.

Hashtables est une structure de données qui supporte la recherche O(1) et l'insertion.

un hashtable a habituellement une clé et une paire de valeurs, où la clé est utilisé comme paramètre à une fonction (une fonction de hachage ) qui va déterminer l'emplacement de la valeur dans sa structure de données interne , généralement un tableau.

comme l'insertion et la recherche dépend seulement sur le résultat de la fonction de hachage et non sur la taille du hachtable ni le nombre d'éléments stockés, un hachtable A O(1) insertion et recherche.

Il y a une mise en garde , cependant. C'est-à-dire que, comme le hashtable devient de plus en plus complet, il y aura collisions de hachage où la fonction de hachage retournera un élément d'un tableau qui est déjà occupé. Cela nécessitera un 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 être effectuée dans le temps O(1). Cependant, bons algorithmes de résolution de collision peut réduire le nombre de tentatives de trouver un autre emplacement vide convenable ou en augmentant la taille du hachoir peut réduire le nombre de collisions en premier lieu.

donc, en théorie, seul un hashtable soutenu par un tableau avec un nombre infini d'éléments et une fonction de hachage parfait serait en mesure d'atteindre la performance O(1) , car c'est la seule façon d'éviter les collisions de hachage qui poussent vers le haut le nombre d'opérations requises. Par conséquent, pour tout tableau de taille finie sera à un moment ou un autre moins que O(1) en raison de collisions de hachage.

voyons un exemple. Utilisons un hashtable pour stocker les" paires 151920920 " suivantes:"

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

nous allons mettre en œuvre le hashtable back-end avec un tableau de 100 éléments.

Le key sera utilisé pour déterminer un élément du tableau pour stocker les ( key , value ) paire. Afin de déterminer la élément, le hash_function sera utilisé:

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

à partir du résultat ci-dessus, nous assignerons les paires (key, value) dans les éléments du tableau.

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

le l'insertion ne nécessite que l'utilisation d'une fonction de hachage, et ne dépend pas de la taille du hachoir ni de ses éléments, de sorte qu'elle peut être effectuée dans le temps O(1).

de Même, la recherche d'un élément utilise la fonction de hachage.

si nous voulons chercher la clé "Name" , nous allons effectuer un hash_function("Name") pour trouver quel élément dans le tableau la valeur désirée réside.

aussi, la recherche ne dépend de la taille du hashtable ou du nombre d'éléments stockés, donc une opération O(1).

tout va bien. Essayons d'ajouter une entrée supplémentaire de ("Pet", "Dog") . Cependant, il y a un problème , comme hash_function("Pet") retourne 18 , qui est le même hachage pour la clé "Name" .

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

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

comme il y a eu une collision de hachage dans cette insertion, notre performance n'était pas tout à fait O(1).

ce problème apparaîtra également lorsque nous tenterons de rechercher la clé "Pet" , car essayer de trouver l'élément contenant la clé "Pet" en exécutant hash_function("Pet") retournera toujours 18 initialement.

une fois nous cherchons l'élément 18, nous trouverons la clé "Name" plutôt que "Pet" . Lorsque nous trouvons cette incohérence, nous aurons besoin de résoudre la collision afin de récupérer l'élément correct qui contient la clé réelle "Pet" . Resovling une collision de hachage est une opération supplémentaire qui rend la table de hachage de ne pas exécuter en O(1) fois.

Je ne peux pas parler aux autres discussions que vous avez vu, mais il y a au moins un algorithme de hachage que est garanti D'être O(1).

Cuckoo hashing maintient un invariant de sorte qu'il n'y a 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 une implémentation de ça, c'est quelque chose qui a été récemment découvert quand j'étais à l'Université. Pour des données relativement statiques ensembles, il devrait être un très bon O(1), car il calcule deux fonctions de hachage, effectue deux recherches, et sait immédiatement la réponse.

remarquez, ceci suppose que le calcul du hash est O(1) aussi bien. Vous pourriez argumenter que pour les chaînes length-K, n'importe quel hachage est minimalement O(K). En réalité, vous pouvez lier K assez facilement, disons K < 1000. O (K) ~= O (1) pour K < 1000.

il peut y avoir une erreur conceptuelle sur la façon dont vous comprenez la notation Big-Oh. Cela signifie que, pour un algorithme et un ensemble de données 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'ensemble de données tend vers l'infini.

quand on dit qu'un algorithme prend du temps O(n), cela signifie que le temps d'exécution du pire cas d'un algorithme dépend linéairement de la taille de l'ensemble d'entrée.

Lorsqu'un algorithme prend O(1) l'heure, la seule chose qu'il signifie, c'est que, étant donné une fonction T(f) qui calcule le moteur d'exécution d'une fonction f(n), il existe un naturel nombre positif k tel que T(f) < k pour toute entrée n. Essentiellement, cela signifie que la limite supérieure du temps d'exécution d'un algorithme ne dépend pas de sa taille, et a une limite finie.

maintenant, cela ne signifie en aucune façon que la limite est petite, juste qu'elle est indépendante de la taille de l'ensemble d'entrée. Donc si je définit artificiellement un K lié pour la taille d'un ensemble de données, alors sa complexité sera O(k) = O(1).

par exemple, rechercher une instance d'une valeur sur une liste lié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 trie comme un dictionnaire (un arbre de caractères, où le noeud de feuille contient la valeur pour la chaîne utilisée comme clé), si le la clé est bornée, alors son temps de recherche peut être considéré O(1) (Si je définis un champ de caractère 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, dans la mesure où vous supposez que la fonction de hachage est bonne (distribuée au hasard) et suffisamment clairsemée pour minimiser les collisions, et que le ressassage est effectué lorsque la structure de données est suffisamment dense, vous pouvez en effet la considérer comme une structure d'accès-Temps O(1).

en conclusion, O (1) le temps peut être surestimé pour beaucoup de choses. Pour les grandes structures de données, la complexité d'une fonction de hachage adéquate peut ne pas être insignifiante, et il existe suffisamment de cas de coin où le nombre de collisions l'amène à se comporter comme une structure de données O(n), et où le ressassage peut devenir prohibitif. Dans ce cas, une structure O(log(n)) Comme un AVL ou un b-tree peut être une alternative supérieure.

en général, je pense que les gens les utilisent comparativement sans égard à l'exactitude. Par exemple, les structures de données basées sur le hachage sont O(1) (Moyenne) si elles sont bien conçues et que vous avez un bon hachage. Si tout Hache à un seul seau, alors il est O(n). En général, bien que l'on utilise un bon algorithme et que les clés soient raisonnablement distribuées, il est donc pratique d'en parler en tant que O(1) sans toutes les qualifications. De même avec les listes, les arbres, etc. Nous avons à l'esprit certaines implémentations et c'est tout simplement plus pratique d'en parler, quand on parle de généralités, sans les qualifications. Si, d'un autre côté, nous discutons d'implémentations spécifiques, alors il vaut probablement mieux être plus précis.

Hashtable looks-ups sont O (1) en ce qui concerne le nombre d'articles dans le tableau, parce que peu importe le nombre d'articles que vous ajoutez à la liste le coût de hachage d'un seul article est à peu près le même, et la création du hachage vous indiquera l'adresse de l'article.

pour répondre à la question de savoir pourquoi ceci est pertinent: L'OP s'est interrogé sur la raison pour laquelle O(1) a semblé être jeté autour si désinvolte alors que dans son esprit, il ne pouvait évidemment pas s'appliquer dans de nombreuses circonstances. Ce la 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 veut pas dire qu'il est constant, seulement qu'il est limité indépendamment des valeurs d'entrée. Strictement parlant, beaucoup d'algorithmes de temps prétendument O(1) ne sont pas réellement O (1) et vont juste si lentement qu'ils sont limités pour toutes les valeurs d'entrée pratiques.

Oui, le ramassage des ordures affecte la complexité asymptotique des algorithmes qui courent dans l'aire de collecte des ordures. Ce n'est pas sans coût, mais c'est très difficile à analyser sans méthodes empiriques, parce que les coûts d'interaction ne sont pas compositionnels.

le temps passé à ramasser les ordures dépend de l'algorithme utilisé. Typiquement les collecteurs d'ordures modernes basculent les modes que la mémoire remplit pour garder ces coûts sous contrôle. Par exemple, une approche commune est d'utiliser un collecteur de copie de style Cheney lorsque la pression de mémoire est faible parce qu'il paie coût proportionnel à la taille de l'ensemble en direct en échange d'utiliser plus d'espace, et de passer à un collecteur de marque et de balayage lorsque la pression de mémoire devient plus grande, parce que même si elle paie coût proportionnel à l'ensemble en direct pour le marquage et à l'ensemble tas ou ensemble mort pour le balayage. Au moment où vous ajoutez le marquage de carte et d'autres optimisations,etc. le coût le plus mauvais cas pour un ramasseur d'ordures pratique peut effectivement être un peu pire, ramasser un facteur logarithmique supplémentaire pour certains modèles d'utilisation.

donc, si vous attribuez une grande table de hachage, même si vous y accédez en utilisant O(1) recherche pour tous les temps au cours de sa vie, si vous le faites dans un environnement de collecte des ordures, de temps en temps les ordures collecteur traversera l'ensemble du tableau, parce qu'il est taille O(n) et vous paierez ce coût périodiquement pendant la collecte.

la raison pour laquelle nous laissons habituellement hors de la l'analyse de la complexité des algorithmes est que la collecte des ordures interagit avec votre algorithme de manière non-triviale. La gravité du coût dépend beaucoup de ce que vous faites d'autre dans le même processus, de sorte que l'analyse n'est pas compositionnelle.

de plus, au-delà de la question de la copie vs. compact vs. mark and sweep, les détails de la mise en œuvre peuvent affecter radicalement les complexités qui en résultent:

1. collecteurs D'ordures supplémentaires qui piste sale bits, etc. on peut tout faire sauf faire disparaître ces plus grandes ré-épreuves.
2. Cela dépend si votre GC fonctionne périodiquement en fonction de l'horloge murale ou exécute proportionnelle au nombre d'allocations.
3. Si une marque et de balayage de style algorithme est concomitante ou stop-the-world
4. S'il marque des allocations fraîches noires s'il les laisse blanches jusqu'à ce qu'il les jette dans un récipient noir.
5. Si votre langue admet des modifications de pointeurs peuvent laisser certains éboueurs travailler en un seul passage.

enfin, lorsque nous discutons d'un algorithme, nous parlons d'un homme de paille. Les asymptotiques n'intégreront jamais complètement toutes les variables de votre environnement. Il est rare que vous mettiez en œuvre tous les détails d'une structure de données telle que conçue. Vous empruntez une fonctionnalité ici et là, vous déposez une table de hachage parce que vous avez besoin d'un accès rapide et sans ordre, vous utilisez un union-trouver sur disjoint ensembles avec compression de chemin et union par rang pour fusionner la mémoire-régions là-bas parce que vous ne pouvez pas vous permettre de payer un coût proportionnel à la taille des régions lorsque vous les fusionner ou ce que vous avez. Ces structures sont des primitives de pensée et les asymptotiques vous aident à planifier les caractéristiques de performance globale pour la structure "dans le grand" mais la connaissance de ce que les constantes sont des questions aussi.

vous pouvez implémenter cette table de hachage avec parfaitement O (1) Caractéristiques asymptotiques, il suffit de ne pas utiliser la collecte des ordures; mapper dans la mémoire à partir d'un fichier et de le gérer vous-même. Vous n'aimerez probablement pas les constantes impliquées.

table de Hachage implémentations sont en pratique pas "exactement" O(1) en cours d'utilisation, si vous testez une de vous les trouverez en moyenne autour de 1,5 recherches pour trouver une clé donnée à travers un grand jeu de données

(en raison du fait que les collisions DO se produisent, et en cas de collision, un emplacement différent doit être assigné)

aussi, dans la pratique, les HashMaps sont soutenus par des tableaux avec une taille initiale, qui est "grown" à la taille double quand il atteint 70% la plénitude en moyenne, ce qui donne un espace d'adressage relativement bon. Après 70% de plénitude, les taux de collision augmentent plus rapidement.

Big O theory déclare que si vous avez un algorithme O(1), ou même un algorithme O (2), le facteur critique est le degré de la relation entre la taille de l'ensemble d'entrée et les étapes pour insérer/récupérer l'un d'eux. O(2) est encore le temps constant, donc nous l'approchons comme O (1), parce qu'il signifie plus ou moins la même chose.

en réalité, il y a seulement 1 façon d'avoir un "hashtable parfait" avec O (1), et qui exige:

1. Un Mondial De Hachage Parfait Générateur De Clé
2. un espace d'adressage illimité.

( cas D'Exception : si vous pouvez calculer à l'avance toutes les permutations de clés autorisées pour le système, et votre espace d'adresse de sauvegarde cible est défini pour être la taille où il peut contenir toutes les clés qui sont autorisées, alors vous pouvez avoir un hachage parfait, mais c'est une perfection" domaine limité")

étant donné une allocation de mémoire fixe, il n'est pas du tout plausible d'avoir ceci, parce qu'il supposerait que vous avez un moyen magique d'empaqueter une quantité infinie de données dans une quantité fixe d'espace sans perte de données, et c'est logistiquement impossible.

donc rétrospectivement, obtenir O (1.5) qui est encore temps constant, dans une quantité limitée de mémoire avec même un relativement Naïve générateur de clés de hachage, je considère plutôt sacrément génial.

Note suffixe Note I use o(1.5) and O(2) here. Ça n'existe pas à big-O. Ce sont simplement ce que les gens qui ne connaissent pas big-o supposent est la raison.

Si quelque chose prend 1,5 étapes pour trouver une clé, ou 2 étapes pour trouver cette clé, ou 1 étapes pour trouver cette clé, mais le nombre d'étapes ne dépasse jamais 2 et si il faut 1 ou de l'étape 2 est complètement au hasard, puis il est encore Big-O O(1). C'est parce que peu importe comment de nombreux articles à vous ajouter à la taille de l'ensemble de données, il maintient toujours les <2 étapes. Si pour toutes les tables > 500 touches il faut 2 pas, alors vous pouvez supposer que ces 2 pas sont en fait un pas avec 2 parties,... qui est toujours en O(1).

si vous ne pouvez pas faire cette hypothèse, alors votre ne pas être grand-o penser du tout, parce qu'alors vous devez utiliser le nombre qui représente le nombre de les étapes de calcul limitées nécessaires pour tout faire et "one-step" est sans signification pour vous. Juste entrer dans votre tête qu'il ya Non corrélation directe entre Big-O et le nombre de cycles d'exécution impliqués.

je pense que quand beaucoup de gens jettent autour du terme" O(1) "Ils ont implicitement à l'esprit une" petite "constante, quoi que" petit " signifie dans leur contexte.

vous devez prendre toute cette analyse big-O avec le contexte et le bon sens. Il peut être un outil extrêmement utile, ou il peut être ridicule, selon la façon dont vous l'utiliser.