代码之家  ›  专栏  ›  技术社区  ›  NaSh

求图中局部最小值/最大值的爬山算法的时间复杂度

theory complexity-theory time-complexity algorithm
  •  3
  • NaSh  · 技术社区  · 9 年前

    在图中找到局部最小值的算法的时间复杂度(算法顺序)是多少 n 节点(每个节点最多 d 邻居)?

    详细信息: 我们有一个图表 n 节点。图中的每个节点都有一个整数值。每个节点最多有 d 邻居。我们正在寻找一个在其邻居中具有最低值的节点。该图由邻接列表表示。该算法首先选择随机节点,然后在这些节点中选择具有最小值的节点 u ). 从节点开始 u ,算法找到邻居 v 哪里 value(v) < value(u) 。然后,它继续 v 并重复上述步骤。当节点没有具有较低值的任何邻居时,算法终止。这个算法的时间复杂度是多少?为什么?

    1 回复  |  直到 9 年前
        1
  •  2
  •   libik    9 年前

    时间复杂度为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的节点,通过所述的alghoritm,将检查所有节点和所有边,直到到达值为1的节点。

    任务的最复杂度:“找到一个元素”是O(N),其中“N”是输入的长度,而输入的长度实际上是 N=G(n,d)=n+d .

    推荐文章
    Suhail Gupta  ·  在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?
    2 年前
    Liana78  ·  查找和最小化合并排序算法运行时分析
    7 年前
    Lamaman  ·  素数算法的复杂度是多少?
    7 年前
    irish Senthil  ·  声明变量是否对大O表示法有效?
    7 年前
    shir k  ·  大阵列中1的θ
    7 年前
    Monk  ·  为什么大Oh不总是算法的最坏情况分析?
    7 年前
    Faisal Alzahrani  ·  用Java计算程序的Big-O
    7 年前
    Dazcii  ·  如何找到3个嵌套循环的复杂性
    7 年前
    svaerth  ·  使用巨型哈希表在多项式时间内求解数独
    7 年前
    shinwari_afg  ·  使用大Oh分析while(key<=N*N)循环的复杂性
    7 年前
    关于  
    代码之家 - 一站式码农服务社区
    沪ICP备11025650号