看到一段有關于算法分析的代碼，帶着注釋：
public class ThreeSum
{
public static int count(int[]a)
{
// 統計和為0的元組數量
int N = a.length;
int cnt = 0;
for (int i =0;i
for(int j=i+1;k
for(int k =j+1;k
if(a[i]+a[j]+a[k]==0)//執行頻率略等于n^3/6
cnt++;
return cnt;
}
public static void main(String[]args)
{
int [] a = In.readInts(args[0]);
StdOut.println(count(a));
}
}
代碼幹的事情就是擷取一組數字然後去找三個和為0的元組數量。想問的是這個執行頻率是怎麼計算的？
拿這部分代碼說事：
for (int i =0;i
for(int j=i+1;k
for(int k =j+1;k
if(a[i]+a[j]+a[k]==0)//執行頻率略等于N^3/6；無法了解。為什麼在這裡是N^3/6，而且/6是怎麼來的？
cnt++;
回答
for (int i =0;i
for(int j=i+1;j
for(int k =j+1;k
你可以這樣來看，如下：
n=1，第一個for循環執行1次，第二個for循環執行0次，第三個for循環不執行，共執行1次。
n=2，第一個for循環執行2次，第二個for循環執行1次，第三個for循環不執行，共執行3次。
n=3，第一個for循環執行3次，第二個for循環執行2次，第三個for循環執行1次，共執行6次。
…..
依次類推：
你看這個就是前n項和的求和公式嘛：(1+n)*n/2 = n^2/2
這注釋應該是從外到内求值計算.
for(i=0; i
{//循環體内執行n次
}
定理1:
前n項和
定理2:
推演通用公式:
for (int i =0;i
for(int j=i+1;k
for(int k =j+1;k
if(a[i]+a[j]+a[k]==0)//n^3/6:1/2(n^2)中的n^2的前n項和為n^3/3再乘以1/2
cnt++;