将数学模型嵌套到数学模型中以计算操作次数

我正在阅读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

将数学模型嵌套到数学模型中以计算操作次数

回答

相关问题