Discussion :

[nadia85]

Bonsoir,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

O(log n)

.

Merci d'avance

[Flodelarab]

Bonjour

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)

[nadia85]

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

[Flodelarab]

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

[WhiteCrow]

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.

[nadia85]

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