我正在寻找PageRank算法的Big-O复杂性。我几乎找不到任何东西，我只是找到了O(n+m)（n - 节点数，m - 弧/边数），但我现在不相信这种复杂性。
我认为它缺少趋同标准。我不认为这是一个常数，我认为收敛取决于图形直径。一次迭代的 Big-O 可能就足够了，那么收敛并不重要。
尽管如此，PageRank 需要接触每个节点并聚合每个传入的排名，所以我期望运行时为 O(n * m) .
我错过了什么吗？有谁知道PageRank的Big-O复杂性的宝贵来源吗？
提前谢谢。
经过一些研究和进一步的思考，我得出的结论是O(n+m)是真实的。
因为即使在一个完整的图表中，也必须触摸每个边缘两次。一个人无法触及每一个边缘，这是我思想上的错误。因此，必须至少触摸每个节点，这是n次，每个边是大O中的m的两倍。所以正确答案是O(n+m)