嵌套循环，多少次运行和复杂度

Question

我有这 2 个代码，问题是找出 x=x+1 在每种情况下会运行多少次，因为 T1(n) 代表代码 1，T2(n) 代表代码2.然后我必须找到每个人的大O，但我知道该怎么做，问题是我一直在寻找有多少次（当然是n） x = x + 1 will 运行.

代码 1：

for( i= 1; i <= n; i++)
    {
    for(j = 1; j <= sqrt(i); j++)
          {
           for( k = 1; k <= n - j + 1; k++)
               {
               x = x + 1;
               }
          }
    }

代码 2：

for(j = 1; j <= n; j++)
   {
    h = n;
    while(h > 0)
        {
        for (i = 1; i <= sqrt(n); i++)
            {
            x = x+1;
            } 
        h = h/2;
        }

   }

我真的很卡，而且已经看了很多所以我问是否有人可以帮助我，请分析解释我。

PS：我认为在代码 2 中，这个 for (i = 1; i <= sqrt(n); i++) 将运行 n*log(n) 次，对吗？然后呢？

Answer 1

对于code 1你有x=x+1的调用次数是：

此处我们将 1+sqrt(2)+...+sqrt(n) 与 n sqrt(n) 划界，并使用了第一项是首项的事实。

对于code 2，计算更简单：

第二个循环实际上是通过迭代 h = h/2 从 h=n 到 0 但你可以看到这与从 1 到 [=19] 是一样的=].我们使用的是 j, t, i 相互独立的事实（类似于我们可以写出 f(n) 的 1 到 n 的总和就是 nf(n)） .

嵌套循环，多少次运行和复杂度

Nested loops, how many times run and complexity

algorithm

complexity-theory

big-o

nested-loops

code-complexity