algorithm - 查找关键比较数 C 和移动数 M

Question

我正在阅读 N.Wirth - Algorithms and Data Structures。 (Oberon version: August 2004)

问题: 他是如何计算这些 C 和 M 的？没有解释这个过程......(任何帮助都会有用)

让我告诉你这是怎么回事...我遇到了以下情况:

2.2.1 Sorting by Straight Insertion

... A good measure of efficiency is obtained by counting the numbers C ofneeded key comparisons and M of moves (transpositions) of items.

他描述了这个算法是如何工作的:

PROCEDURE StraightInsertion; 
 VAR i, j: INTEGER; x: Item; 
BEGIN 
 FOR i := 1 TO n-1 DO 
 x := a[i]; j := i; 
 WHILE (j > 0) & (x < a[j-1] DO a[j] := a[j-1]; DEC(j) END ; 
 a[j] := x 
 END 
END StraightInsertion

...然后他讲述了C 和M。但他没有解释找到它们的过程 --> 他只是展示了计数的 Cmin、Mmax...:

Analysis of straight insertion. The number Ci of key comparisons in the i-th sift is at most i-1, at least 1, and --- assuming that all permutations of the n keys are equally probable --- i/2 in the average. The number Mi of moves (assignments of items) is Ci + 2 (including the sentinel). Therefore, the total numbers of comparisons and moves are:

Cmin = n-1                   Mmin = 3*(n-1) 
Cave = (n^2 + n - 2)/4       Mave = (n^2 + 9n - 10)/4 
Cmax = (n^2 + n - 4)/4       Mmax = (n^2 + 3n - 4)/2 

那么问题是:他是如何计算这些C和M的？他没有解释找到所有这些数字的过程。你能帮我了解如何找到它们吗？任何帮助都是好的。

附言我一直在寻找关于这个主题的信息，但没有结果。

---

另外:

以下是随机选择八个数字(如果需要)的示例所示的插入过程:

Initial Keys: 44 55 12 42 94 18 06 67
                 v
          i=1 44 55 12 42 94 18 06 67
                    v
              v-----<   
          i=2 12 44 55 42 94 18 06 67 
                       v
                 v-----<   
          i=3 12 42 44 55 94 18 06 67
                          v
          i=4 12 42 44 55 94 18 06 67
                             v
                 v-----------<    
          i=5 12 18 42 44 55 94 06 67
                                v
              v-----------------<    
          i=6 06 12 18 42 44 55 94 67
                                   v
                                v--<    
          i=7 06 12 18 42 44 55 67 94

Answer 1

C 是比较次数，M 是移动的数据项数。如果我们以您的示例为例，在第 1 次迭代中，有 1 次比较并且没有移动。在第 2 次迭代中，有 2 次比较和 2 次移动。等等。现在，让我们考虑第 k 次迭代。将进行 k 次比较，并假设您的确切位置是从 1 到 k 的中间位置，将进行 k/2 次移动。数C和M是k从1变为n时所有比较和移动的总和。您所要做的就是将总和相加，k 从 1 到 n 变化，您就得到了数字。