Calculating the number of times the if statement is executed
This code counts how many integer triple sums are 0: Full code here .
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++;
}
}
}
}
Now, from the book "Algorithms" by Robert Sedgwick, I read:
- The initialization
cnt
to0
is executed exactly once. -
cnt++
runs from 0 to the number of times a triple is found. - The if statement is executed
n(n-1)(n-2)/6
once.
I have done some experiments and they are all correct. But I am completely unaware of how they calculate the number of times the if statement has been executed. I'm not sure, but I think that:
-
n
meansi to n
-
(n-1)
means fromi+1
ton
-
(n-2)
means fromj+1
ton
-
/6
I don't know what it is for.
Can someone explain how to calculate this?
source to share
This is the sum of the amounts.
- The inner loop runs
n-j-1
once every time it is reached - The middle cycle runs
n-i-1
once every time it is reached - The outer loop is executed
n
once.
Add all of these and you will get the total number of times it is called cnt++
.
Please note that the number of times the average cycle is performed every time, do not n-1
it n-i-1
, where i
- the index of the outer loop. Likewise for the middle cycle.
The factor /6
comes from taking it into account in the summation formula.
source to share
This can be seen as a combinatorial combination . To select 3 unique items from n
items ( k=3
in the linked article) will give you n!/(n-3)! = n*(n-1)*(n-2)
options. However, in the code, the order of 3 items does not matter. There are permutations for each combination of 3 elements 3! = 6
. Therefore, we need to divide by 6 to get only free features. So we getn!/(3!(n-3)!) = n(n-1)(n-2)/6
source to share
The first loop runs for N times (0 to N-1)
Outer loop execution time:
Fi(0) + Fi(1) + Fi(2)...Fi(N-1)
When i
- 0
, the middle cycle performs N-1
once (from 1 to N-1)
When i
1
, the middle cycle performs N-2
once (from 2 to N-1)
...
Average cycle time:
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)
Now let's move on to the innermost loop:
When j
- 1
, the inner loop executes N-2
once (2 to N-2)
When j
2
, the inner loop executes N-3
once (3 to 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
You can also check: Formula for calculating the sum of squares of the first N natural numbers and the sum of the first N natural numbers .
Alternative explanation:
You find all pairs of triplets. This can be done in paths N C 3... those. (N) * (N-1) * (N-2) / (1 * 2 * 3)
ways.
source to share
In your code where i is executed from 0 to n, j from i to n, k from j to n, the if statement is executed approximately n ^ 3/6 times. To understand why this is the case, look at this code, which will obviously execute an if statement just as often:
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++;
}
}
}
}
}
The inner loop is now obviously executing n ^ 3 times. The if statement is executed if i <j <k. We ignore the case when i == j or i == k or j == k. The three variables i, j and k can be sorted in six different orders (i <j <k, i <j, j <i <k, etc.). Since each of these six different sorting orders occurs equally often, about n ^ 3/6 times we have the order i <j <k.
source to share