我试图确定TextRank的空间和时间复杂度本文中列出的算法：https://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf
由于它使用的PageRank的复杂度为：O（nm）（n - 节点数，m - 弧/边数），我们在迭代中运行它/直到收敛关键字提取的复杂性我认为它将是：O （i *（nm））并且使用邻接矩阵将空间复杂度设为O（V ^ 2）
对于句子提取，我相信它会是同样的事情 .
我真的不确定，任何帮助都会很棒谢谢你 .
我试图确定TextRank的空间和时间复杂度本文中列出的算法：https://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf
由于它使用的PageRank的复杂度为：O（nm）（n - 节点数，m - 弧/边数），我们在迭代中运行它/直到收敛关键字提取的复杂性我认为它将是：O （i *（nm））并且使用邻接矩阵将空间复杂度设为O（V ^ 2）
对于句子提取，我相信它会是同样的事情 .
我真的不确定，任何帮助都会很棒谢谢你 .
1 回答
如果你重复T次算法（内部）的复杂度为O（nm），或者其他任何相关问题，那么得出结论新算法（外部）将具有O（T *（nm））的复杂度是正确的 . ：
外部算法每次重复内部算法时只会增加一个常量的复杂性 .
参数n和m在内部算法的每次调用时保持不变 .
换句话说，外部算法应该在恒定时间内为内部算法准备输入，并且新输入的参数应该在T次迭代中保持由n和m很好地表示 . 否则，如果这两个要求中的任何一个未能得到证实，那么你应该将与新参数相关的复杂性加以T倍
并且还考虑了在使用内部之前和之后外部算法的所有预处理和后处理 .