以 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.

Answer 2

第二个例子的答案不是nlogn。您不能简单地将两个 for 循环的边界相乘。第二个循环形成一个 sigma，因为第二个循环从 1 移动到 i，最多可以是 nlogn。这个 sigma 是 1+2+...+nlogn... 这个 sigma 的总和可以用自然数和的公式求出。因此西格玛是 (nlogn*(nlogn+1))/2.

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

How many times is x=x+1 executed in theta notation in terms of n?

algorithm

language-agnostic

time-complexity

complexity-theory

analysis