algorithm - 关于算法的时间复杂度

Question

下面问题的时间复杂度是多少。

int j=1;
while(j<n){
  j+=log(j+5);
}

Answer 1

通过展开和的前三项:

你可以看到它只是 log(log(j)) 的迭代的总和。由于 O(j) >> O(log(j))，因此 O(log(j)) >> O(log(log(j))；因此，第一项掩盖了所有其他项。

因此总和为O(log(j))，这意味着时间复杂度为

.

数值测试表明，这实际上是 O(n^0.82...)。