algorithm - 什么是 PageRanks Big-O 复杂度？

Question

我正在寻找 PageRank 算法的 Big-O 复杂度。我几乎找不到任何东西，我只是找到了O(n+m)（n- 节点数，m- 弧/边数），但我现在不相信这种复杂性。

我认为它缺少收敛标准。我不认为这是一个常数，我认为收敛取决于图形直径。一次迭代使用 Big-O 可能就足够了，那么收敛并不重要。

尽管如此，PageRank 需要触及每个节点并聚合每个传入的排名，所以我预计运行时间为O(n * m).

我错过了什么？有人知道 PageRank 的 Big-O 复杂性的宝贵来源吗？

提前致谢。

Answer 1

经过一番研究和进一步思考，我得出的结论是O(n+m)真实的。

因为即使在完整的图中，也必须触摸每条边两次。一个人无法触及每一个边缘，那是我的想法的错误。因此，一个人必须至少接触每个节点，这是 n 次，每个边是大 O 中 m 的两倍。所以正确答案是O(n+m)