algorithm - 确定和分析这些不同循环的大 O 运行时

Question

这是简单的代码，我想找出代码的时间复杂度我已经分析过了，我的老师告诉我其中有一个错误。我不知道我哪里错了。需要帮助。谢谢

j = 2
while(j<n)
{
    k=j
    while(k < n) 
    {
        sum + = a[k]*b[k]
        k = k*k
    }
    k = log(n)
    j += log(k)
}

这是我得到的答案

时间复杂度 = O(n/loglogn)。

我只想知道我哪里错了

Answer 1

你从 2 到 n，每一步都将 log log n 添加到累加器，所以你确实有 n/log 记录 n 个步骤。

然而，每一步做了什么？每一步，您都从 j 到 n，每一步都将累加器乘以自身。那是多少操作？ 我不是 100% 确定，但基于一些乱七八糟的 this answer ，这似乎最终成为 log log (n - j) 步骤，或简称为 log log n。

因此，n/log log n 步骤，每一步执行 log log n 操作，给你一个 O(n/log log n * log log n)，或者O(n)算法。

---

一些实验似乎或多或少证实了这一点(Python)，尽管 n_ops 似乎随着 n 变大而有点标记:

import math

def doit(n):
    n_ops = 0

    j = 2
    while j < n:
        k = j
        while k < n:
            # sum + = a[k]*b[k]
            k = k*k
            n_ops += 1

        k = math.log(n, 2)
        j += math.log(k, 2)
        n_ops += 1

    return n_ops

结果:

>>> doit(100)
76
>>> doit(1000)
614
>>> doit(10000)
5389
>>> doit(100000)
49418
>>> doit(1000000)
463527