Il n'y a pas de résumé de la notation O pour les opérations sur les structures de données les plus courantes, y compris les tableaux, les listes chaînées, les tables de hachage, etc ...Quelle est la complexité temporelle de l'indexation, de l'insertion et de la suppression de structures de données communes?
Je suppose que je vais commencer avec la complexité temporelle d'une liste chaînée:
indexation ----> O (n)
Insertion/suppression à la fin ----> O (1) ou O (n)
Insertion/Suppression en milieu ---> O (1) avec l'itérateur O (n) sans out
La complexité temporelle pour l'insertion à la fin se termine si vous avez l'emplacement du dernier nœud, si vous le faites, ce serait O (1) sinon vous devrez chercher dans la liste chaînée et la complexité du temps passerait à O (n).
Amorti Big-O pour hashtables:
Notez qu'il existe est un facteur constant pour l'algorithme de hachage, et l'amortissement signifie que la performance mesurée réelle peut varier considérablement.
Qu'est-ce que Big-O d'insertion de N éléments dans un ensemble de hachage? Réfléchissez deux fois –
Amorti, c'est N. Vous pouvez avoir des problèmes avec le redimensionnement de la matrice de sauvegarde, cependant. En outre, cela dépend de votre méthode de gestion des conflits. Si vous faites un chaînage et que votre algorithme d'insertion de chaînage est N (comme à la fin d'une liste chaînée), il peut être transféré dans N^2. –
C'est faux. Vous avez la mauvaise définition de «amortissement». Amorti signifie le temps total pour faire un tas d'opérations divisé par le nombre d'opérations. La performance la plus défavorable pour l'insertion de N éléments est définitivement O (N^2), pas O (N). Donc les opérations ci-dessus sont toujours O (n) pires, amorties ou non. Vous le confondez avec la complexité temporelle "moyenne" en supposant une certaine distribution des fonctions de hachage, qui est O (1). – newacct
arbres rouge-noir:
Gardez à À moins que vous n'écriviez votre propre structure de données (par exemple, une liste chaînée en C), cela peut dépendre de manière dramatique de la mise en œuvre de structures de données dans votre langue/cadre de choix. À titre d'exemple, jetez un oeil à la benchmarks of Apple's CFArray over at Ridiculous Fish. Dans ce cas, le type de données, un CFArray du framework CoreFoundation d'Apple, modifie en fait les structures de données en fonction du nombre d'objets présents dans le tableau, passant d'un temps linéaire à un temps constant autour de 30 000 objets.
Ceci est en fait l'une des belles choses sur la programmation orientée objet - vous n'avez pas besoin de savoir comment il fonctionne, juste que cela fonctionne, et « comment cela fonctionne » peut changer en fonction des besoins .
information sur ce sujet est maintenant disponible sur Wikipédia: Search data structure
+----------------------+----------+------------+----------+--------------+
| | Insert | Delete | Search | Space Usage |
+----------------------+----------+------------+----------+--------------+
| Unsorted array | O(1) | O(1) | O(n) | O(n) |
| Value-indexed array | O(1) | O(1) | O(1) | O(n) |
| Sorted array | O(n) | O(n) | O(log n) | O(n) |
| Unsorted linked list | O(1)* | O(1)* | O(n) | O(n) |
| Sorted linked list | O(n)* | O(1)* | O(n) | O(n) |
| Balanced binary tree | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(log n) | O(log n)** | O(n) | O(n) |
| Hash table | O(1) | O(1) | O(1) | O(n) |
+----------------------+----------+------------+----------+--------------+
* The cost to add or delete an element into a known location in the list (i.e. if you have an iterator to the location) is O(1). If you don't know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time.
** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element.
Il y a une certaine confusion dans la suppression dans le tableau. Certains disent, il faut O (n) temps pour trouver l'élément que vous voulez supprimer. Ensuite, afin de le supprimer, vous devez déplacer tous les éléments vers la droite d'un espace vers la gauche. C'est aussi O (n) donc la complexité totale est linéaire. Et aussi certains disent, pas besoin de remplir l'espace vide, il peut être rempli par le dernier élément. –
En outre, que faire si nous voulons insérer un élément dans un tableau à une première position? Cela ne provoquerait-il pas le décalage de l'ensemble du tableau? Donc, ne devrait pas O (n) être le temps d'insertion pour un tableau? –
Notez que vous devez * distinguer * entre un ** non trié ** et un ** tableau trié **. Le décalage/remplissage des éléments du tableau n'est qu'une préoccupation d'un tableau trié, donc la complexité linéaire au lieu de 'O (1)' sur un tableau non trié. En ce qui concerne votre idée de trouver l'élément que vous voulez supprimer, vous devez à nouveau faire la distinction entre ** trouver ** un élément et ** le supprimer **. La complexité pour la suppression suppose que vous connaissez déjà l'élément que vous allez supprimer, c'est pourquoi vous avez 'O (n)' sur un tableau trié (nécessite un décalage) et 'O (1)' sur un tableau non trié. – Mobiletainment
La complexité de l'insertion dans le milieu ** ** d'une liste singulièrement liée est O (n). Si la liste est doublement liée et que vous savez que le noeud que vous voulez insérer est O (1) –
j'avais oublié d'ajouter la partie de l'itérateur. Merci de le signaler –
@Rob: il peut être un doute stupide, mais je ne suis pas capable de comprendre comment pouvez-vous insérer dans la liste doublement liée dans O (1)? Si j'ai 1 ' 4' et si je dois insérer 5 entre 3 et 4, et tout ce que j'ai est pointeur sur le nœud de tête (c'est-à-dire 1) je dois traverser dans O (n). Ai-je raté quelque chose? – Bhushan