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

Question

我有这2个代码，问题是要找出每次x = x + 1将运行多少次，因为T1（n）代表代码1和T2（n）代表代码2.然后我必须找到每一个的BIG O，但我知道该怎么做，事情是我被困在找到多少次（当然n）x = x + 1会跑。

CODE 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电话的号码是：

在这里，我们n sqrt(n)界1+sqrt(2)+...+sqrt(n)和使用的事实，第一项是首项。

对于code 2计算是简单的：

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