提问人：Thibault de Villèle 提问时间：11/25/2017 最后编辑：Thibault de Villèle 更新时间：11/26/2017 访问量：522
如何根据增量值确定算法的时间复杂度
How to determine the time complexity of an algorithm depending on a delta value
问：
我现在必须研究PageRank，我已经编写了这个算法：
我已经确定了 while 循环内部的复杂性，我相信是 .但后来我被 while 循环本身的复杂性所困扰，它本质上是由 delta 决定的。Delta 是迭代时 R 和 R 迭代时 R 的 L1 范数之差。O(n^2)ii+1
有没有办法确定这种复杂性？
编辑：更多解释：
- R 是秩向量
- epsilon 是用户给出的值（我们希望 epsilon 很小，以便对 PageRank 有很好的估计，但又不能太小，需要很长时间才能计算出来）
creerMatricePageRank()为我们创建邻接矩阵，并在混合中添加秩源向量E- A 是邻接矩阵
答：
0赞
An0num0us
11/25/2017
#1
最里面的从 0 到 ，这意味着 。外层从 0 到 ，表示 。fortO(t)fortO(t) * O(t) = O(t^2)
然后你有另一个在时间上什么都不做。它不执行任何操作，因为它首先计算，然后语句将值分配给 to（现在两者相等）。下一个语句是说 == .forO(t)d2d1d2delta = |d1 - d2|delta = |delta - delta|delta = 0
如果 epsilon 为负数，则循环永无止境，否则循环在一次迭代后结束，这意味着复杂性。whileO(t^2)
您的代码显然有问题。你要么根本不需要这个循环，要么你混淆了分配。while
评论
0赞
Thibault de Villèle
11/26/2017
哦，是的，对不起。我混淆了第 20 行的位置。它应该在循环计算之前。但即便如此，当算法依赖于增量值时，有没有一种方法可以确定算法的复杂性？d2
评论