我該如何正式解釋一些操作？

Question

考慮下面的代碼：

Function Fun(int n) { 
    int j, k, t=1; 
    for (j=0; j<=4*n^2; j+=4) { 
     for (k=j; k<=4*sqrt(n); k+=4) { 
      t+=8; 
     } 
    } 
} 

我想算命令t+=8;多少次被執行。

我發現，通過n嘗試幾個值，它是執行：

倍。但是，我怎麼才能正式解釋呢？

Answer 1

這一部分：

for (j=0; j<=4*n^2; j+=4){ 
    for (k=j; k<=4*sqrt(n); k+=4){ 
     t+=8; 
    } 
} 

足以回答你的問題。

注意，它是類似於：

for (j=0; j<=n^2; j++){ 
    for (k=4*j; k<=4*sqrt(n); k+=4){ 
     t+=8; 
    } 
} 

其類似於：

for (j=0; j<=n^2; j++){ 
    for (k=j; k<=sqrt(n); k++){ 
     t+=8; 
    } 
} 

1）第一for示出了第二個被執行多少次

2）第二個for顯示執行t+=8;多少次

讓我們解釋公式的兩個部分：

• 第二部分是與你的第二for： k取Math.floor(Math.sqrt(n)) - j + 1值步驟j（當j=0 =>Math.floor(Math.sqrt(n)) + 1值）
• 第一部分與您的第一個for有關。但是爲什麼你有sqrt(n)而不是n^2？這是棘手的部分。如果分析第二個循環何時生效，則會看到大於sqrt(n)的任何j都是無用的（因爲k的上限爲sqrt(n)，所以第二個「for content」未執行。這就是爲什麼在公式中你有sqrt(n)。

這事，因爲你的代碼就是類似於：

for (j=0; j<=sqrt(n); j++){ 
    for (k=j; k<=sqrt(n); k++){ 
     t+=8; 
    } 
}