Mat*_*cke 7 algorithm pagerank graph time-complexity graph-algorithm
我正在寻找PageRank算法的Big-O复杂性.我几乎找不到任何东西,我刚刚发现O(n+m)(n- 节点数,m- 弧/边数)但我现在还不相信这种复杂性.
我认为它缺少收敛标准.我不认为这是一个常数,我认为收敛取决于图形直径.将Big-O用于一次迭代可能就足够了,然后收敛并不重要.
然而,PageRank需要触及每个节点并聚合每个传入的排名,所以我期望运行时间O(n * m).
我错过了什么？有没有人知道PageRank的Big-O复杂性的宝贵来源？
提前致谢.
经过一番研究和进一步思考，我得出的结论是，这O(n+m)是真实的。
因为即使在完整的图中，人们也必须触摸每条边两次。一个人不能触及每一个边缘，这是我的想法的错误。因此，一个人必须至少接触每个节点，这是大O中的n次和每条边的两次，即m次。所以正确答案是O(n+m)