gpt4 book ai didi

algorithm - 对程序的总复杂度求和时处理常量

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:23:41 25 4
gpt4 key购买 nike

我编写了一个程序,用于在图上执行 BFS(广度优先搜索)。程序的执行分为初始化阶段和算法阶段。假设 V 是顶点数,E 是边数:我已经计算出初始化的复杂度为 O(V+2E),算法的复杂度为 O(V+E)。这种情况下整个程序的复杂度是多少?

最佳答案

它将是O(V+E)。常量在大 O 表示法中被忽略:

O(cf(x)) = O(f(x))
c*O(f(x)) = O(f(x))

当然,c应该是一个常量。

关于algorithm - 对程序的总复杂度求和时处理常量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29170898/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com