Thanks to everyone who came here and gave me time.

I read Robert Sedgwick (s ++) 2014, p. 31, Lemma 1.2.

An example of solving a connectivity problem using the fast merge method is given.

for(i = p; i != id[i]; i = id[i]) ; for(j = q; j != id[j]; j = id[j]) ; if(i == j) continue; id[i] = j;

With this, everything is clear, then he writes about the effectiveness of the algorithm:

For M pairs of N objects, when M> N, the solution of the connectivity problem by the fast combining algorithm may require executing more than MN / 2 instructions.

He says about M pairs, are they the right pairs and not the right ones? Those who just come to the input?

Suppose that pairs are entered in the following order (1-2 2-3 3-4) and so on. After entering N-1 such pairs, we get N objects belonging to the same set, and the tree formed by the fast combining algorithm is a straight line, where object N points to object N-1, which, in turn, refers to object N-2, the one on the N-3 and so on. To perform a search operation for an object N, the program must go through the N-1 pointers. Thus, the average number of pointers on which the transitions are performed for the first N pairs is (0 + 1 + ... (N-1)) / N = (N-1) / 2

Why does he find the arithmetic average ?! After all, he says that the list is built (1-2 2-3 3-4) and so on, to go from start to finish you need to go N-1 times. It is not clear that he has entered the "transitions for the first N pairs"?

Now suppose that all other pairs associate an object N with some other object. To perform a search operation for each of these pairs, it is necessary to go at least along N-1 indicators. The grand total for M search operations with such a sequence of input pairs is definitely greater than MN / 2

What does he have to enter "all other pairs", wrong pairs in the input? How did he get the MN / 2?

Maybe I was stupid somewhere, help please.

    2 answers 2

    He says about M pairs, are they the right pairs and not the right ones? Those who just come to the input?

    What is, in your understanding, the "wrong" pairs? There is no division of pairs into regular ones and no, there are only vertices and edges of the graph.

    Why does he find the arithmetic average ?! After all, he says that the list is built (1-2 2-3 3-4) and so on, to go from start to finish you need to go N-1 times.

    It is, I remind you, about the time estimate. The program performs N merge operations - each operation takes some time. So that you can say something about the execution time of the operation as a whole, you need to average these values. Then the arithmetic mean.

    It is not clear that he has entered the "transitions for the first N pairs"? What does he have to enter "all other pairs", wrong pairs in the input? How did he get the MN / 2?

    The author considers such a sequence of pairs at the input of the algorithm as an example of a “bad” sequence:

    1. first comes the N-1 pair - (1,2), (2,3), ..., (N-1, N);
    2. then comes M-N + 1 pair of the form (*, N).

    Each pair is processed by your algorithm. The "transition" is an iteration of one of the for loops in the first two lines.

    So, for the pair (4,5) from the first block, you will have to go through 4-3-2-1 (5 are not connected with anyone yet), only 3 transitions.

    For the pair (4, N) from the second block, you will have to go through 4-3-2-1 first, and then another N- (N-1) -...- 4-3-2-1, total N + 2 transitions.

    • Right / wrong - I thought so when I read "For M pairs of N objects, when M> N", he wrote earlier that "the algorithm for solving the connectivity problem never outputs more than N-1 pairs, because as soon as it outputs N-1 pairs , any pair encountered after this will be already connected "already connected - wrong," if (i == j) continue; " From the beginning N-1 pair - (1,2), (2,3), ..., (N-1, N), then all the "wrong" connections. - uskabuska pm
    • Why find the mean? Please indicate where the operations are different? ; c - uskabuska
    • one
      For the pair (1,2) no transitions are performed, for the pair (2,3), 1 transition is made, then 2, 3, etc. to N-1 transition. - Pavel Mayorov
    • Where is 1 transition? savepic.ru/7332262.png Maybe you had to enter the "synchronization" of the number of iterations between 2 cycles? Therefore, the average is? - uskabuska
    • But in this example, there is no difference between them. (look at the picture, please) - uskabuska

    He simply first considered the group of the first X unions, and then the group of other Y. From the property of the first group, he derived that the number of operations for each union call in the second group is limited to the number below (X - 1), from which he received at least Y ( X - 1) operations. Just a little liberty of the language.

    UPD: from the second fourth edition:

    Again, we’re suppose that we’ve been able to connect with the single component. An immediate implication of the PROPOSITION G is the running time of the quadratic, in the worst case. Suppose that the input pairs come in the order of 0-1, then 0-2, then 0-3, and o forth. After the N - 1, it has been defined that it has been defined as the N-1, with 0 linking to 1, which links to 2, which links to 2 , and so forth (see the diagram on the facing page). By the PROPOSITION G, it is 2i + 3 (for the pair 0 i is the depth for the pair. Thus, it is (3 + 5 + 7 + ... + 2N + 1) ~ N ^ 2.

    Apparently, indeed, in the first edition it was poorly understood, therefore in the second fourth example they were completely reworked :) I can only advise you to order the second edition, this is a recognized masterpiece.

    • Found on the Internet only in 2014 and 2011, and what is your edition? - uskabuska
    • one
      @uskabuska fourth edition, 2014 - Alexei Averchenko