將數學模型嵌套到數學模型中以計算操作次數

我正在閱讀Sedgewick和Wayne的書「算法 - 第四版」，我必須承認「算法分析」一章中的某些部分讓我感到困惑！這可能是由於我缺乏數學知識......反正！將數學模型嵌套到數學模型中以計算操作次數

書中的某個地方有一個程序的例子，其中內循環被認爲是正好執行N（N-1）（N-2）/ 6次。那就是：

public static int count(int[] a) { 
     int count = 0; 

     for (int i = 0; i < a.length; i++) { 
      for (int j = i + 1; i < a.length; j++) { 
       for (int k = j + 1; k < a.length; k++) { 
        if (a[i] + a[j] + a[k] == 0) { 
         count++; 
        } 
       } 
      } 
     } 
     return count; 
    }

我熟悉的大O符號，但是當涉及到循環計數opreations的確切數目，我迷路了。我瞭解N（N-1）（N-2）部分，但爲什麼我們必須除以6？它背後的邏輯是什麼？

任何幫助將不勝感激！

來源

2012-08-11 stzzz1

參見[*算法§1.4分析*]（HTTP：//algs4.cs .princeton.edu/14analysis /）和['ThreeSum']（http://algs4.cs.princeton.edu/14analysis/ThreeSum.java.html）。 – trashgod 2012-08-11 15:11:58

如果你能理解N(N-1)(N-2)一部分，這裏有一個想法：

採取組合3號，I，J，K，無論3落入從另一個範圍0 <= i,j,k < N和不同的一個（這也是在代碼照顧，這就是爲什麼公式是N(N-1)(N-2)，而不是N^3。

現在，讓我們說的數字是13，17，42，它並不真正的問題whoch數字他們是在多少種方法你把它們放在一起？

13-17-42 
13-42-17 
17-13-42 
17-42-13 
42-13-17 
42-17-13

六！

這些方式中有多少可以出現在代碼中？只有一個！（這在j和k的初始化時已經被關注）。所以N(N-1)(N-2)的總數除以6。

來源

2012-08-11 14:37:29

你的帖子完全合理，我明白了！謝謝！ – stzzz1 2012-08-11 15:09:01

你是我的英雄。我讀過關於這個的19個解釋，而你是第一個真正有意義的解釋。 – ellotheth 2013-08-27 04:05:56

正如我們所知道...

1 + 2 + 3 + 4 ... + N => N（N-1）/ 2

類似地，最內層循環作品像

1.N + 2（N-1）3（N-2）+ ... N.1 => N（N-1）（N-2）/ 6

這是proof爲此。

來源

2012-08-11 14:37:52 SiB

6從3派生！（三個因子來自三個循環）。

考慮最外層的循環，比如說5個元素的數組。對於方程的那一部分，你計算N = 5，但是隻有值i = 0，i = 1或i = 2時才能到達內部循環。同樣，你用（N-1）表示下一個循環，但是你只能到達內部循環的值j = 1，j = 2或j = 3，而不是（N-1）隱含的四個值）。

除以6（對於三個循環）可補償在到達最內循環之前將耗盡數組中值的值。

來源

2012-08-11 15:23:01 phatfingers

您可以使用六西格瑪符號和探索如何拿出你的書提到的公式：

enter image description here

來源

2014-06-06 16:10:11

將數學模型嵌套到數學模型中以計算操作次數

回答

相關問題