关于算法的时间复杂度

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...)。

Answer 2

使用编辑后的代码（+= 而不是 =），我推测这段代码的渐近时间复杂度（假设 log() 和其他基本操作取常量时间）是 Θ(n / log n).

很容易证明循环至少需要 n / log(n+5) = n / (log n × log 5) 迭代完成，因为它计数到 n，每次迭代递增计数器数量严格小于 log(n+5)。因此，渐近时间复杂度为至少 Ω(n / log n).

表明它也是 O(n / log n)，因此 Θ(n / log n), 似乎有点棘手。基本上，我的论点是，对于足够大的 n，从 exp(k 递增计数器 j ) 直到 exp(k+1) 的顺序为 C × exp(k) / k 次迭代（常数 C ≈ (1 − exp(−1)) / 5，如果我没记错的话）。让 h = ceil(log(n))，将计数器从 1 递增到 n 因此需要最多

T = C × ( exp(h) / h + exp(h−1) / (h−1) + exp(h−2 ) / (h−2) + … + exp(1) / 1 )

迭代。对于大 n（因此 h），前导 exp(h) / h项应该支配其余项，这样T≤C₂× exp(h) / h 对于某个常数 C₂，因此循环应该运行 in O(exp(h) / h) = O( n / log n) 时间.

也就是说，我承认这只是一个证明草图，我的论点可能存在漏洞或错误。特别是，我实际上还没有确定常量（？）C₂ 的上限。 (C₂ = C × h 显然满足不等式，但只会在运行时间产生 O(n) 上限；C₂ = C / (1 − exp(−1)) 会给出所需的界限，但显然太低了。）因此，我不能完全排除这种可能性实际时间复杂度可能（非常小）更高。

关于算法的时间复杂度

About time complexity of algorithm

algorithm

math

computer-science

time-complexity