Quelles sont les complexités temporelles des différentes structures de données?

Question

J'essaie de temps en liste complexité des opérations de structures de données communes comme les Tableaux, les Binaires de Recherche, Arbres, Tas, Liste chaînée, etc. et surtout, je me réfère à Java. Ils sont très communs, mais je suppose que certains d'entre nous ne sont pas 100% confiants quant à la réponse exacte. Toute aide, en particulier des références, est grandement apprécié.

E. g. Pour la seule liste liée: Modification d'un élément interne est O(1). Comment pouvez-vous le faire? Vous AVEZ à la recherche de l'élément avant de le changer. Aussi, pour le Vecteur, l'ajout d'un élément interne est donnée en O(n). Mais pourquoi ne pouvons-nous pas faire en temps constant amorti à l'aide de l'index? S'il vous plaît corrigez-moi si je suis absent quelque chose.

Je suis poster mes résultats/devine que la première réponse.

Answer 1

Les tableaux

• Ensemble, Vérifier l' élément à un index particulier: O(1)
• Recherche: O(n) si le tableau est trié et O(log n) si le tableau est trié et quelque chose comme une recherche binaire est utilisé,
• Comme l'a souligné Aivean, il n'y a pas d' Delete opérations sur les Tableaux. On peut symboliquement supprimer un élément en paramètre à une valeur précise, par exemple, -1, 0, etc. en fonction de nos besoins
• De même, Insert pour les tableaux est fondamentalement Set comme mentionné au début,

Liste de tableaux:

• Ajouter: Amorti O(1)
• Supprimer: O(n)
• Contient: O(n)
• Taille: S(1)

Liste Liée:

• Insertion: O(1), si elle est effectuée à la tête, O(n) si n'importe où ailleurs, puisque nous avons à atteindre cette position par traveseing la linkedlist de façon linéaire.
• Suppression: O(1), si elle est effectuée à la tête, O(n) si n'importe où ailleurs, puisque nous avons à atteindre cette position par traveseing la linkedlist de façon linéaire.
• Recherche: O(n)

Doublement Lié Liste:

• Insertion: O(1), si la tête et la queue, O(n) si n'importe où ailleurs, puisque nous avons à atteindre cette position par traveseing la linkedlist de façon linéaire.
• Suppression: O(1), si la tête et la queue, O(n) si n'importe où ailleurs, puisque nous avons à atteindre cette position par traveseing la linkedlist de façon linéaire.
• Recherche: O(n)

Pile:

• Push: O(1)
• Pop: O(1)
• Haut: O(1)
• Recherche (quelque Chose comme de recherche, comme une opération spéciale): O(n) (j'imagine que oui)

File D'Attente/Deque/File D'Attente Circulaire:

• Insérer: O(1)
• Supprimer: O(1)
• Taille: S(1)

Un Arbre De Recherche Binaire:

• Insérer, supprimer et rechercher: Moyenne des cas: O(log n), le Pire Cas: O(n)

Rouge-Noir Arbre:

• Insérer, supprimer et rechercher: Moyenne des cas: O(log n), le Pire Cas: O(log n)

Tas/PriorityQueue (min/max):

• findMin/findMax: O(1)
• insérer: O(log n)
• deleteMin/Max: O(log n)
• de recherche, supprimer (si fourni): O(n), nous aurons à analyser tous les éléments, car ils ne sont pas classées comme BST

HashMap/Hashtable/HashSet:

• Insérer/Supprimer: O(1) amorti
• Re-taille/hash: O(n)
• Contient: O(1)