Complexité temporelle de l'algorithme Hill Climbing pour trouver local min/max dans un graphique

Question

Quelle est la complexité temporelle (ordre d'algorithme) d'un algorithme qui trouve le minimum local dans un graphique avec n nœuds (ayant chaque nœud un maximum de d voisins)?

Détail: Nous avons un graphique avec n nœuds. Chaque noeud du graphe a une valeur entière. Chaque noeud a un maximum de d voisins. Nous recherchons un nœud ayant la valeur la plus faible parmi ses voisins. Le graphique est représenté par une liste d'adjacence. L'algorithme commence par sélectionner des nœuds aléatoires et, au sein de ces nœuds, il sélectionne le nœud avec une valeur minimale (disons le nœud u). À partir du noeud u, l'algorithme trouve un voisin v, où value(v) < value(u). Ensuite, il continue avec v et répète l'étape ci-dessus. L'algorithme se termine lorsque le nœud n'a aucun voisin avec une valeur inférieure. Quelle est la complexité temporelle de cet algorithme et pourquoi?

Answer 1

complexité est en O (n + d), parce que vous pouvez avoir n nœuds, qui sont connectés comme cela, le nombre indique la valeur du noeud:

16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-1 

Et vous pouvez choisir au hasard ceux-ci, marqué par "!"

!-!-!-13-12-11-10-9-8-7-6-5-4-3-2-1 

Vous sélectionnez le nœud avec la valeur 14 et par décrit alghoritm, vous allez vérifier tous les nœuds et tous les bords jusqu'à ce que vous atteignez le nœud avec la valeur 1.

La pire complexité de la tâche: " trouver un élément "est O (N), où" N "est la longueur de votre entrée et la longueur de votre entrée est réellement N=G(n,d)=n+d.