algorithm - 嵌套循环，运行次数和复杂度

Question

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

代码 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=nto 进行的，但是您可以看到这与从to 进行相同。我们使用的是相互独立的事实（类似地，就像我们可以将总和从to of写为 just 一样）。0h = h/21log nj, t, i1nf(n)nf(n)