algorithm - 用n表示，θ= x + 1执行过几次？

我在夏天学习数据分析和算法。
问题是：用n来表示x=x+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乘以（lgn）^3，但那可能是3（n^2）lgn吗然后第三行是n，所以它们的组合是526*n^3（lgn）^3，加上n就等于。我不确定。
同时也要确保我理解我遇到的这类问题

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

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

最佳答案

回答第一部分：

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*（lgn）^3次。
说到大θ符号，
当n>1时，n总是大于（lgn），所以，

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

对于一些正常数c1526，大θ表示法是
θ（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.

关于algorithm - 用n表示，θ= x + 1执行过几次？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30341014/