algorithm - 以 n 表示的 theta 表示法中 x=x+1 执行了多少次？

Question

我在夏季学习数据分析和算法。

问题:针对语句 x = x + 1 的执行次数，找到一个以 n 表示的 Θ 符号。

for i = 1 to 526
    for j = 1 to n^2(lgn)^3
       for k = 1 to n 
           x=x+1

我对如何找到答案感到困惑。第一行是 526，那么第二行显然是 n^2 倍 (lgn)^3，但那可能是 3(n^2)lgn 吗？然后第三行就是n。如此组合它们将是 526*n^3(lgn)^3，而只有 n 将类似于 Θ(n^3)(lgn)^3。我不确定。

还要确保我理解我遇到的这类问题

for i = 1 to |nlgn| 
    for j = 1 to i
        x=x+1

答案只是 nlgn，因为第二行的 i 并不重要，对吧？

Answer 1

回答第一部分:-

for i = 1 to 526
for j = 1 to n^2(lgn)^3
   for k = 1 to n 
       x=x+1

这个程序将运行 526 * n^2 * (lg n)^3 * n 次 = 526 * n^3 * (lg n)^3 次。

所以，x = x +1 将被执行 526 * n^3 * (lg n)^3 次。

使用 Big-theta 符号，

对于任何 n>1，n 总是大于 (lg n)，所以，

  c1 * n^3 <= 526 * n^3 * (lg n)^3 <= c2 * n^3 * (lg n)^3

对于一些正常数 c1<526 和 c2>526，所以 big-theta 符号将是

θ(n^3*(lg n)^3).

回答第二部分，

for i = 1 to |nlgn| 
for j = 1 to i
    x=x+1

您的假设完全不正确。由 j 引导的内循环对于计算 x = x+1 语句也是必要的，因为它是内循环的主体，而内循环本身是外循环的主体。

所以，在这里，x = x + 1 将被计算为

= 1 + 2 + ... + n*(lg(n) times
= [n*lg(n) * {n*lg(n)}+1]/2 times.