什么是PageRanks大O复杂性？
什么是PageRanks大O复杂性？
提问于 2012-09-18 17:44:43
我在寻找PageRank算法的大O复杂度。我几乎找不到任何东西，我只找到了O(n+m) ( n -节点的数量，m -弧/边的数量)，但我现在还不相信这种复杂性。
我认为它缺少收敛标准。我不认为这是一个常数，我认为收敛性取决于图的直径。一次迭代的大O可能就足够了，那么收敛性就不重要了。
尽管如此，PageRank需要接触到每个节点并聚合每个传入的等级，所以我期望有一个O(n * m)的运行时。
我错过了什么吗？有没有人知道PageRank的大O复杂性的有价值的来源？
提前谢谢。
Stack Overflow用户
回答已采纳
发布于 2012-09-24 19:09:41
经过一些研究和进一步的思考，我得出结论，O(n+m)是真正的东西。
因为即使是在一个完整的图中，每条边也要接触两次。一个人不可能触及每一个边缘，这是我的想法中的错误。因此，人们必须至少接触每个节点，这是n次，每条边两次，这是大O中的m。所以正确的答案是O(n+m)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12474398
复制相关文章
相似问题
腾讯云开发者
