给定算法的时间复杂度是多少？

Question

x=0
for i=1 to ceiling(log(n))
    for j=1 to i
        for k=1 to 10
            x=x+1

我已经把我想出的答案放在这里了：

我认为时间复杂度是θ(n^2 log(n))，但我不确定我的逻辑是否正确。如果能帮助我理解如何进行此类分析，我将不胜感激！

Answer 1

你有三个循环。让我们一一考虑。

最内层循环：它独立于n或i，并且会运行总是10次。所以这个循环的时间复杂度是Theta(10).

最外层循环：这个循环的时间复杂度非常简单，就是Theta(logn)。

中间循环：由于i的值可以达到logn，这个循环的时间复杂度也是O(logn)

总体复杂度：Theta(logn)*O(logn)*Theta(10)或O(logn*logn*10)或10*O((logn)^2)或O((logn)^2)

Answer 2

最外层循环将运行进行 ceil(log n) 次。中间循环取决于 i 的值。

因此，它的行为将是：

1st iteration of outermost-loop    - 1
2nd iteration of outermost-loop    - 2
.....................................
ceil(log n) iteration of outermost-loop     - ceil(log n)

最内层循环独立于其他变量，每次中间循环迭代总是运行 10 次。

因此，净迭代

= [1*10 + 2*10 + 3*10 + ... + ceil(log n)*10] 
= 10 * {1+2+...+ceil(log n)}
= 10 * { (ceil(log n) * ceil(log n)+1)/2} times
= 5 * [ceil(log n)]^2 + 5 * ceil(log n)
= Big-Theta {(log n)^2}
= Θ{(log n)^2}.

希望您清楚这一点。因此，您的回答是错误的。

给定算法的时间复杂度是多少？

What is the time complexity of the given algorthm?

algorithm

complexity-theory

time-complexity

big-theta

asymptotic-complexity