在具有 n 的图中找到局部最小值的算法的时间复杂度(算法阶数)是多少？节点(每个节点最多有 d 个邻居)？
详细信息:我们有一个图表 n节点。图中的每个节点都有一个整数值。每个节点最多有 d邻居。我们正在寻找在其邻居中具有最低值的节点。该图由邻接表表示。该算法首先选择随机节点，然后在这些节点中选择具有最小值的节点(假设节点 u )。从节点 u 开始, 该算法找到一个邻居 v , 其中value(v) < value(u) .然后，它继续 v并重复上述步骤。当节点没有任何具有较低值的邻居时，算法终止。这个算法的时间复杂度是多少？为什么？
最佳答案
时间复杂度是O(n + d)，因为你可以有n个节点，它们是这样连接的，数字表示节点的值:
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 的节点，并通过描述的算法，您将检查所有节点和所有边，直到到达值为 1 的节点。
任务的最复杂性:“找到一个元素”是 O(N)，其中“N”是输入的长度，输入的长度实际上是 N=G(n,d)=n +d.
关于algorithm - 用于在图中查找局部最小值/最大值的爬山算法的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34881625/