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

Question

J'ai remarqué de très étranges utilisation de O(1) lors de la discussion des algorithmes impliquant hachage et les types de recherche, souvent dans le contexte de l'utilisation d'un dictionnaire de type fourni par le système de la langue, ou à l'aide du dictionnaire ou de hachage-tableau des types utilisés à l'aide du tableau de l'index de la notation.

Fondamentalement, O(1) signifie bornée par une constante de temps et (généralement) fixe de l'espace. Quelques jolies opérations fondamentales sont en O(1), bien que l'utilisation d'intermédiaire langues étrangères et VMs tend à déformer sa pensée (par exemple, comment fait-on à amortir le garbage collector et d'autres processus dynamiques sur ce qui serait autrement O(1) activités).

Mais en ignorant l'amortissement des latences, garbage collection, et ainsi de suite, je ne comprends toujours pas comment le saut à l'hypothèse que certaines techniques qui impliquent un certain type de recherche peut être O(1) sauf dans des conditions très spéciales.

Bien que j'ai remarqué cela avant, un exemple qui vient d'être montré à l' Pandincus question, "Bon" collection à utiliser pour obtenir des éléments en O(1) de temps en C# .NET?".

Comme je l'ai dit il, la seule collection que je connaisse qui offre O(1) accès garanti lié fixe lié tableau avec un index entier valeur. La présomption est que le tableau est mis en œuvre par certains de cartographie de la mémoire d'accès aléatoire qui utilise O(1) opérations pour localiser la cellule ayant l'indice.

Pour les collections qui implique une certaine forme de recherche pour déterminer l'emplacement d'un correspondant de la cellule pour un autre type d'indice (ou pour un tableau fragmenté avec index entier), la vie n'est pas si facile. En particulier, si il y a des collisons et la congestion est possible, l'accès n'est pas exactement O(1). Et si la collection est souple, on doit reconnaître et d'amortir le coût de l'extension de la structure sous-jacente (comme un arbre ou une table de hachage) pour lequel soulagement de la congestion (par exemple, la collision de l'incidence d'arbres ou de déséquilibre).

Je n'aurais jamais pensé à parler de ces flexible et dynamique des structures de O(1). Pourtant, je les vois offert comme O(1) des solutions sans identification des conditions qui doivent être maintenues pour avoir O(1) l'accès doit être assuré (ainsi que la constante d'être négligeable).

LA QUESTION: l'Ensemble de cette préparation est vraiment pour une question. Qu'est-ce que le laisser-aller autour de O(1) et pourquoi est-elle acceptée si aveuglément? Est-il reconnu que même O(1) peut être considérée comme indésirable gros, même si à peu près constante? Ou est O(1), il suffit de l'appropriation d'un calcul de complexité de la notion d'informel utiliser? Je suis perplexe.

Mise à JOUR: les Réponses et Les commentaires du point où j'étais décontracté sur la définition de O(1) moi-même, et j'ai réparé ça. Je suis toujours à la recherche de bonnes réponses, et une partie des commentaires, les threads sont plutôt plus intéressant que leurs réponses, dans quelques cas.

Answer 1

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

O(1) le pire des cas

C'est simple - toutes les opérations sont pas plus que d'une quantité constante de temps dans le pire des cas, et donc dans tous les cas. Accéder à un élément d'un tableau est O(1) des cas les pires.

O(1) amorti pire des cas

Amorti signifie que chaque opération est - O(1) dans le pire des cas, mais pour n'importe quelle séquence de N opérations, le coût total de la séquence n' 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.

Par exemple, la norme de Tableau Dynamique qui double sa capacité lorsqu'il se remplit exige O(1) amorti temps d'insérer un élément à la fin, même si certaines insertions exiger O(N) du temps - il y a toujours assez d' O(1) insertions que l'insertion de N éléments prend toujours O(N) du temps total.

O(1) cas moyen

Celui-ci est la plus délicate. Il y a deux définitions possibles de la moyenne-cas: l'un pour les algorithmes randomisés avec des entrées fixes, et un pour des algorithmes déterministes avec randomisés entrées.

Pour les algorithmes randomisés avec des entrées fixes, nous pouvons calculer la moyenne des cas les temps d'exécution pour toute donnée entrée par l'analyse de l'algorithme et de la détermination de la distribution de probabilité possibles de tous les temps de course et de prendre la moyenne sur cette distribution (en fonction de l'algorithme, il peut ou peut ne pas être possible en raison du Problème de l'Arrêt).

Dans les autres cas, nous avons besoin d'une distribution de probabilité sur les entrées. Par exemple, si nous avons été à la mesure d'un algorithme de tri, une telle distribution de probabilité serait de la distribution qui a tous les N! les permutations possibles de l'entrée tout aussi probable. Ensuite, le cas moyen temps de course est la moyenne des temps d'exécution sur toutes les entrées possibles, pondérée par la probabilité de chaque entrée.

Puisque l'objet 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, on ne peut pas toujours déterminer la distribution de probabilité des entrées parce que, eh bien, nous pourrions être de hachage à peu près tout, et ces éléments pourrait être à venir à partir d'un utilisateur de taper dans ou à partir d'un fichier système. Donc, quand on parle de tables de hachage, la plupart des gens simplement supposer que les entrées sont bien comportés et de la fonction de hachage est bien comporté, tels que la valeur de hachage de toute entrée est essentiellement aléatoire distribuée uniformément sur la plage de valeurs de hachage.

Prenez un instant et laissez ce dernier point évier en O(1) moyenne de cas de performance pour les tables de hachage vient d'en supposant que toutes les valeurs de hachage sont distribuées de manière uniforme. Si cette hypothèse est violée (qui elle n'est généralement pas, mais il peut certainement arriver, et il arrive), le temps d'exécution est plus O(1) en moyenne.

Voir aussi le Déni de Service par la Complexité Algorithmique. Dans ce papier, les auteurs discutent de la façon dont ils ont exploité des failles dans les fonctions de hachage par défaut utilisé par les deux versions de Perl pour générer un grand nombre de chaînes avec des collisions de hachage. Armé avec cette liste de chaînes, ils ont généré un déni de service (ddos) sur certains serveurs web en les nourrissant de ces chaînes qui ont abouti, dans le pire des cas O(N) comportement dans les tables de hachage utilisé par les serveurs web.

Answer 2

D'après ce que j'ai compris, la valeur O(1) n'est pas nécessairement constante ; elle ne dépend pas des variables considérées. Ainsi, on peut dire qu'une recherche par hachage est O(1) en ce qui concerne le nombre d'éléments dans le hachage, mais pas en ce qui concerne la longueur des données hachées ou le rapport entre les éléments et les godets dans le hachage.

L'autre élément de confusion réside dans le fait que la notation "big O" décrit un comportement limitatif. Ainsi, une fonction f(N) pour de petites valeurs de N peut effectivement présenter de grandes variations, mais il serait toujours correct de dire qu'elle est O(1) si la limite lorsque N s'approche de l'infini est constante par rapport à N.

Answer 3

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

Il s'agit de deux déclarations distinctes. On peut avoir O(1) dans le temps mais O(n) dans l'espace ou autre.

Est-il reconnu que même O(1) peut être excessivement grand, même s'il est quasi constant ?

O(1) peut être incroyablement ÉNORME et il s'agit toujours de O(1). On néglige souvent le fait que si l'on sait que l'on aura 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, il s'agit d'un équilibre entre les deux. Un algorithme O(n !) peut être plus performant qu'un algorithme 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é - et non du temps que prendra un algorithme, ou une mesure pure de la "qualité" d'un algorithme donné pour un objectif donné.

Answer 4

Je vois ce que vous voulez dire, mais je pense qu'il y a quelques hypothèses de base qui sous-tendent l'affirmation selon laquelle les consultations 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 clés est pratiquement distribué au hasard, ou du moins n'est pas conçu à dessein pour que la fonction de hachage soit peu performante.

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

Answer 5

Tables de hachage est une structure de données qui permet une recherche et une insertion O(1).

Une table de hachage se compose généralement d'une paire clé/valeur, où l'élément est utilisée comme paramètre d'une fonction (une touche 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 ou du nombre d'éléments stockés, une table de hachage a une capacité d'insertion et de recherche O(1).

Il y a un mise en garde Toutefois, il n'y a pas de raison de s'inquiéter. C'est-à-dire qu'au fur et à mesure que la table de hachage se remplit, il y aura collisions de hachage où la fonction de hachage renvoie un élément d'un tableau déjà occupé. Cela nécessitera un résolution des collisions 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 en O(1) temps. Cependant, de bons algorithmes de résolution des collisions peut réduire le nombre de tentatives pour trouver un autre emplacement libre et convenable ou l'augmentation de la taille de la table de hachage peut réduire le nombre de collisions.

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 une performance O(1) car c'est le seul moyen d'éviter les collisions de hachage qui augmentent le nombre d'opérations nécessaires. Par conséquent, pour tout tableau de taille finie, le nombre d'opérations sera à un moment ou à un autre inférieur à O(1) en raison des collisions de hachage.

---

Prenons un exemple. Utilisons une table de hachage pour stocker ce qui suit (key, value) paires :

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

Nous allons implémenter le back-end hashtable avec un tableau de 100 éléments.

En key sera utilisé pour déterminer un élément du tableau dans lequel stocker le ( key , value ). Afin de déterminer l'élément, le hash_function sera utilisé :

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

À partir du résultat ci-dessus, nous assignerons à l'élément (key, value) dans les é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, de sorte qu'elle peut être réalisée en O(1) temps.

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

Si nous voulons rechercher la clé "Name" nous effectuerons une hash_function("Name") pour trouver l'élément du tableau où se trouve la valeur souhaitée.

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

Tout va bien. Essayons d'ajouter une entrée supplémentaire de ("Pet", "Dog") . Il y a cependant un problème, car hash_function("Pet") retours 18 qui est le même hash pour le "Name" clé.

Nous devons donc résoudre cette collision de hachage. Supposons que la fonction de résolution des collisions de hachage que nous avons utilisée ait trouvé que le nouvel élément vide est 29 :

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

Étant donné qu'il y a eu une collision de hachage lors de cette insertion, notre performance n'est pas tout à fait O(1).

Ce problème se posera également lorsque nous essaierons de rechercher l'élément "Pet" comme s'il s'agissait de trouver l'élément contenant la clé "Pet" en effectuant hash_function("Pet") renverra toujours 18 initialement.

En consultant l'élément 18, nous trouverons la clé "Name" plutôt que "Pet" . Lorsque nous constatons cette incohérence, nous devons résoudre la collision afin de récupérer l'élément correct qui contient le véritable "Pet" clé. Le rétablissement d'une collision de hachage est une opération supplémentaire qui fait que la table de hachage ne fonctionne pas en temps O(1).