我正在搜索 PageRank 算法的大 O 复杂性。
我几乎找不到任何东西，我只是找到了 O(n+m)(n - 节点数，m - 弧/边数) 但我现在还不相信这种复杂性。
我认为它缺少收敛标准。我不认为这是一个常数，我认为收敛取决于图形直径。一次迭代有 Big-O 可能就足够了，那么收敛性就不重要了。
尽管如此，PageRank 需要接触每个节点并聚合每个传入排名，因此我预计运行时间为 O(n * m)。
我错过了什么吗？有人知道 PageRank 的 Big-O 复杂性的宝贵来源吗？
提前致谢。
最佳答案
经过一些研究和进一步思考，我得出的结论是 O(n+m) 是真实的东西。
因为即使在一个完整的图中，也必须触及每条边两次。一个人不能触及每一个边缘，那是我思想上的错误。因此，必须至少接触每个节点，这是 n 次，是大 O 中 m 的每个边的两倍。
所以正确答案是O(n+m)
关于algorithm - 什么是 PageRanks Big-O 复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12474398/