嵌套循環，多少次運行和複雜性

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)）。