Complexité de recherche dans un tableau trié

Bonsoir,

j'aimerais comprendre pourquoi la complexité de l'algorithme de recherche dans un tableau trié et dans une file de priorité est

Code:

---

O(log n)

---

.

Merci d'avance

Bonjour :coucou:

Parce que, comme tu es dans des structures ordonnées, tu peux utiliser la dichotomie ? Ton espace est divisé par deux à chaque fois. Ce n'est pas linéaire. Démultiplier le nombre d'objets ne démultiplie pas ton temps de recherche en proportion. (Toutes ses phrases expriment la même chose de manière différente)

Bonsoir,

D'abord merci pour votre réponse.
Et pour la file de priorité? On la considère comme un tableau trié d'où la complexité de recherche est réduite en O(log(n))?


Merci d'avance

Si c'est la même chose, elles ont la même complexité. Jusqu'ici, tout est logique.

Bonjour,
dans une file de priorité on ne s'intéresse qu'à l'extremum (minimum ou maximum en général), récupérer cette valeur se fait en temps constant = O(1) dans la majorité des implémentations classiques.
Cette structure de donnée n'est pas utilisée pour une recherche plus générale.

Bonsoir,

J'ai voulu comprendre la complexité de recherche dans une file de priorité car j'ai trouvé que dans l'algorithme de dijkstra la complexité du calcul du plus court chemin entre deux sommets dans un graphe G est de l'ordre de O(m x log(n) ) où n est le nombre de sommets et m est le nombre d'arcs. Ce qui est bien meilleur que O(n²) où on utilise des boucles imbriquées pour la recherche.

Merci

Là c'est parce que les opérations d'insertion et suppression sont en O( log n ) dans le cas d'une implémentation classique de la file de priorité avec un tas binaire.
En général on utilise V (pour vertex = nœud) et E (pour edge = arc) dans la littérature.

Pourriez-vous m'indiquer un lien qui explique la complexité d'insertion et de suppression dans une file de priorité classique?

Merci d'avance

heu … google est ton ami :)

par exemple le premier lien lorsque tu cherches «priority queue» donne un lien vers wikipedia ⇒ https://en.wikipedia.org/wiki/Priority_queue

bonjour,

Merci