Временная сложность алгоритма Hill Climbing для нахождения локального минимума/максимума в графике

Question

Какова сложность времени (алгоритм) алгоритма, который находит локальный минимум в графе с узлами n (каждый узел имеет максимум d соседи)?

Деталь: У нас есть график с n узлов. Каждый узел в графе имеет целочисленное значение. Каждый узел имеет максимум d соседей. Мы ищем узел, который имеет самое низкое значение среди своих соседей. Граф представлен списком смежности. Алгоритм начинается с выбора случайных узлов и в пределах этих узлов выбирает узел с минимальным значением (скажем, узел u). Начиная с узла u, алгоритм находит соседа v, где value(v) < value(u). Затем он продолжается с v и повторяет вышеуказанный шаг. Алгоритм завершается, когда узел не имеет ни одного соседа с более низким значением. Какова временная сложность этого алгоритма и почему?

Answer 1

Временная сложность представляет собой О (п + д), так как вы можете иметь п узлов, которые соединены, как это, число показывает значение узла:

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

И вы можете случайным образом выбирать эти, отмеченные от "!"

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

Таким образом, вы выберите узел со значением 14 и описанным alghoritm, вы будете проверять все узлы и все ребра, пока не достигнете узла со значением 1.

Худшей сложностью задания: " найти один элемент "- это O (N), где" N "- длина вашего ввода, а длина вашего ввода - фактически N=G(n,d)=n+d.