嵌套循环成数学模型来计算操作的次数 [英] Nested loops into mathematical model to count number of operations

问题描述

我在读这本书的算法 - 第四版由塞奇威克和韦恩，我必须承认，在算法分析一章中的某些部分是困惑我！这可能是由于我缺乏数学知识造成的......反正！

I'm reading the book 'Algorithms - Fourth edition' by Sedgewick and Wayne and I must admit that some parts in the "Analysis of Algorithms" chapter are confusing me! This is probably caused by my lack of mathematical knowledge... Anyways!

某处在这本书中，有一个程序，其中内环被说成是正确地执行了N（N-1）（N-2）/ 6倍的例子。在这里，它是：

Somewhere in the book, there is an example of a program where the inner loop is said to be executed exactly N(N-1)(N-2)/6 times. Here it is:

    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符号，但是当涉及到​​计算循环中邻preations的确切数目，我迷路了。据我所知，N（N-1）（N-2）的一部分，但为什么我们6分？什么是其背后的逻辑是什么？

I am familiar with the big O notation but when it comes to counting the exact number of opreations in loops, I'm lost. I understand the N(N-1)(N-2) part but why do we have to divide by 6? What is the logic behind it?

任何帮助将是很大的AP preciated！

Any help would be greatly appreciated!

推荐答案

如果你能理解的 N（N-1）（N-2）部分，这里有一个思想：

If you can understand the N(N-1)(N-2) part, here's a thought:

取3个数字的组合，I，J，K，无论3落入范围 0℃= I，J，K＆LT; ñ和从另一个不同的一个（这也照顾了code，这就是为什么公式为 N（N-1）（N-2），而不是 N R个3 。

Take a combination of 3 numbers, i, j, k, whatever 3 that fall into the range 0 <= i,j,k < N and different one from another (this is also taken care in the code and that's why the formula is N(N-1)(N-2) and not N^3.

现在，让我们说的数字是13，17，42，它并不真正的问题whoch号码他们。有多少种方法可以在你把他们在网上？

Now, lets say the numbers are 13, 17, 42. It doesn't really matters whoch numbers they are. In how many ways can you put them in line?

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

六！

如何对这些方法很多可以出现在code？只有一个！ （这是照顾在Ĵ和 K 的initializaton）。

How many of these ways can appear in the code? Only one! (that's taken care in the initializaton of j and k).

所以，总数 N（N-1）（N-2）应分 6 。

这篇关于嵌套循环成数学模型来计算操作的次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！