計算執行if語句的次數

此代碼計算總共有多少個整數三元組爲0：完整代碼爲here。計算執行if語句的次數

initialise an int array of length n 
int cnt = 0 // cnt is the number of triples that sum to 0 
for (int i = 0; i < n; i++) { 
    for (int j = i+1; j < n; j++) { 
     for (int k = j+1; k < n; k++) { 
      if (array[i]+array[j]+array[k] == 0) { 
       cnt++; 
      } 
     } 
    } 
}

現在，由羅伯特·塞奇威克書的算法，我讀到：

的cnt到0初始化只執行一次。
cnt++從0開始執行三次找到的次數。
if語句執行n(n-1)(n-2)/6次。

我已經做了一些實驗，他們都是真實的。但我完全不知道他們如何計算if語句執行的次數。我不知道，但我認爲：

n指從i to n
(n-1)指從i+1到n
(n-2)指從j+1到n
/6我不知道什麼是根本這是爲了。

任何人都可以解釋如何計算這個？

來源

2015-05-07 morbidCode

部分表達式/ 6意味着除以6.參見二項式係數。從{0，...，n-1}中選擇3個元素的任何方法都對應於i，j和k中的一個選擇。 –

您不能將公式歸於循環變量（即，e'（n-1）'並不意味着'i + 1到n'或者（n-2）'不意味着'（j + 1）到n'），請看作爲求和結果的公式，在鏈接@amit張貼 – EvenPrime

這是總和。

內環執行正在達到
中間循環執行正在達到
外環執行n倍它每次n-i-1倍它每次n-j-1次。

Sum all of these你得到的總次數是cnt++被調用。

注意的倍中間環路的數量每次執行不n-1，它是n-i-1，其中i是外循環的索引。中間循環也是如此。

/6因素來自總和公式中的考慮因素。

來源

2015-05-07 12:42:25 amit

好的，但我仍然不明白爲什麼我們除以6.我們怎麼得到6？ – morbidCode

應該是：「** if **執行的次數」 – DrKoch

@morbidCode Look編輯。認爲中間循環不運行'n-1'次，它運行'n-i-1'次。然後你們總結他們所有的總和公式，以得到答案。 – amit

這個公式的基礎來自於級數的總和：

1+2 = 3 
1+2+3 = 6 
1+2+3+4 = 10

存在着公式：

Sum(1..N) == N*(N+1)/2 

1+2+3+4 = 4*5/2 = 10

用遞歸的進展（如在這種情況下）你會得到另一個公式爲了總和。

來源

2015-05-07 12:59:37 DrKoch

這可以被視爲combinatorial問題。從n項目（k=3中鏈接的文章中）選擇3個獨特的項目給出n!/(n-3)! = n*(n-1)*(n-2)的可能性。但是，在代碼中，3個項目的順序無關緊要。對於3個項目的每個組合，存在3! = 6排列。所以我們需要用6除以得到無序的可能性。所以我們得到n!/(3!(n-3)!) = n(n-1)(n-2)/6

來源

2015-05-07 13:00:25 Marein

你最後一段似乎很困惑。在for循環中，變量i，j和k被限制爲小於n，因此不存在索引超出範圍異常。 –

你說得對，我修好了。 – Marein

除以6來自i

在你的代碼中，我從0運行到n，j從i運行到n，k從j運行到n，if語句被執行大約n^3/6次。要知道爲什麼是這樣的話，看一下這個代碼，這顯然也經常執行的if語句：

int cnt = 0 // cnt is the number of triples that sum to 0 
for (int i = 0; i < n; i++) { 
    for (int j = 0; j < n; j++) { 
     for (int k = 0; k < n; k++) { 
      if (j > i && k > j) { 
       if (array[i]+array[j]+array[k] == 0) { 
        cnt++; 
       } 
      } 
     } 
    } 
}

內環顯然現在執行ñ^ 3倍。 if語句被執行如果我< j < k。我們忽略了i == j或i == k或j == k的情況。三個變量i，j和k可以以六個不同的順序排序（i < j < k，i < k < j，j < i < k等）。由於這六個不同的排序順序中的每一個都經常發生，所以大約n^3/6次我們有訂單i < k < k。

來源

2015-05-07 13:19:48 gnasher729

首先循環執行N次（0至N-1）

時間來執行外環是：

Fi(0) + Fi(1) + Fi(2)...Fi(N-1)

i時是0，中間循環執行N-1倍（1至N- 1）
當i是1，中間循環執行N-2倍（2到N-1）
...

時間來執行中間循環爲：

Fi(0) = Fj(1) + Fj(2) ... Fj(N-1) 
Fi(1) = Fj(2) + Fj(3) ... Fj(N-1) 
Fi(0) + Fi(1) + Fi(2)...Fi(N-1) = Fj(1) + 2Fj(2) + ... (N-1)Fj(N-1)

現在來到最內層循環：

當j是1，內環執行N-2倍（2〜N-2）
當j是2，內環執行N-3倍（3至N-2）
...

Fj(1) = Fk(2) + Fk(3) ... Fk(N-1) = 2 + 3 + ... N-1 
Fj(2) = Fk(3) + Fk(4) ... Fk(N-1) = 3 + 4 + ... N-1 
Fj(1) + 2Fj(2) + ... (N-1)Fj(N-1) = (2 + 3 + ... N-1) + (3 + 4 + ... N-1) ... (N-1) 
    = 1 x 2 + 2 x 3 + 3 x 4 .... (N-2) x (N-1) 
    = 1x1 + 2x2 + 3x3 + 4x4 .... (N-1)*(N-1) - (1 + 2 + 3 + 4 + N-1) 
    = (N-1) N (N+1)/6 - N (N-1)/2 
    = N (N-1) ((N+1)/2 - 1/2) 
    = N (N-1) (N-2)/6

您可能還想檢查：公式來計算first N natural numbers的平方和和first N natural numbers的總和。

另一種解釋：

您發現所有對三胞胎。這可以在^N C 方式中完成。即(N) * (N-1) * (N-2)/(1 * 2 * 3)方式。

來源

2015-05-07 13:23:03

計算執行if語句的次數

回答

相關問題