确定以下算法的运行时复杂度

Question

我必须确定以下算法的运行时复杂度（见图）。我知道理论上该怎么做，但对于这个具体示例，我遇到了困难，也没有示例解决方案来查看我是否正确。

如果有人可以查看我的答案并进行更正，甚至可以对正确的解决方案进行解释，我们将不胜感激。

    Overall --> Θ(n^2)
    for(int i=42; i<n*Math.log(n); i++)Θ(n)  
        foo(i);                        Θ(n*log2(n))
        for(int j=1; j<4711; j=j*3)    Θ(n)
            bar(i*j);                  Θ(log2(n))


foo(int n)                             --> Θ(n*log2(n))
    if(n%2 == 0)                       Θ(1)
        for(int i=1; i<2*n; i=i+2)     Θ(n)
            bar(i);                    Θ(log2(n))
    else                               --> Θ(n*log2(n))
        for(int i=1; i<n; i++)         Θ(n)
            bar(n);                    Θ(log2(n))

bar(int m)                              --> Θ(log2(n))
     while(m>0)                         Θ(log2(n))
         m = m/4;                       Θ(1)

Answer 1

bar(int m) 的时间复杂度为 O(log(m))。它实际上是 log_4(m)，但是它可以像这样转换为以 2 为底的对数：log_4(m) = log_2(m) / log_2(4)。而 log_2(4) 是常数。因此它是 O(log(m))。你的分析是正确的。
foo(int n)的时间复杂度是这样计算的：第一个循环，我们从1开始，两个两个的走到2n。它需要 n 次迭代。在第二个循环中，我们从 1 开始，一个一个地走到 n。它需要 n 次迭代。 bar(n) 的复杂度是 O(log(n))。然而 bar(i) 的复杂度取决于 i，而不是 n。是 O(log(i))。所以操作总数可以这样计算：
如果 n 是偶数，则总操作数：
log(1) + log(3) + ... + log(2n) = A
现在，我们知道 A <= nlog(2n) = O(nlogn)。
我们也知道A >= log(1) + log(2)+ ... + log(n) = log(n!) = nlogn = O(nlogn)。 (*)
因此我们将 A 挤在 O(nlogn) 和 O(nlogn) 之间，因此 A 的时间复杂度是 O(nlogn)。
如果 n 是奇数，则为：
log(n) + log(n) + ... + log(n) = nlog(n) 您对第二部分的时间复杂度分析完全正确。
我们调用 foo(i) 大约 nlog(n) 次。然后我们调用 bar(i*j) 8 次。请注意，随着 n 的增加，此值不会改变。因此我们可以忽略 j 因为它不是真正基于输入大小的变量。 bar(i*j) 的时间复杂度与 log(i) 成正比。
所以总的来说，如果 i 是偶数。操作次数：
ilog(i) + 8 * log(i)。
i 为奇数时也是如此。总计：
ilog(i) 从 i=42 到 i=nlog(n)
的总和 42log(42) + 43log(43) + ... + nlog(n)log(nlog(n)) <= nlog(n)*nlog(n)*log(nlog(n)) = O(n^2 * log(n)^3))
整个函数的时间复杂度为O(n^2 * log(n)^3)。

(*) 如果您想知道我们是如何从 log(n!) 切换到 nlog(n) 的。参考Is log(n!) = Θ(n·log(n))?

确定以下算法的运行时复杂度

Determine runtime complexity of following algorithm

algorithm

runtime

complexity-theory