[合并计数[C ++]中如何计算比较次数和移动次数（掉期）

Question

我正在尝试计算合并排序中的交换和比较次数。

#include<iostream>

using namespace std;

int comparisons = 0;
int moves = 0;

void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int* L = new int[n1];
    int* R = new int[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            moves++;
            i++;
        }
        else
        {
            arr[k] = R[j];
            moves++;
            j++;
        }
        k++;
        comparisons++;
    }

    while (i < n1)
    {
        arr[k] = L[i];
        moves++;
        i++;
        k++;
    }

    while (j < n2)
    {
        arr[k] = R[j];
        moves++;
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

int main()
{
    int size;
    cout << "Enter size: " << endl;
    cin >> size;

    int* arr = new int[size];

    for (int i = 0; i < size; i++) {
        arr[i] = rand() % 100;
    }

    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }

    cout << endl << endl;

    mergeSort(arr, 0, size - 1);

    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }

    delete[] arr;

    cout << endl;

    cout << "The number of comparisons: " << comparisons << endl;
    cout << "The number of moves: " << moves << endl;

    cout << endl;

    system("pause");
    return 0;
}

如果我制作一个由10个元素组成的数组，则比较次数应为10 * log2（10）= 33（公式：比较次数= n * log2n）。我的程序输出24，所以不正确。移动数应为2 * 10 * log2（10）= 66（公式：移动数= n * log2n）并且我的程序输出34，所以它也是不正确的。请向我解释如何正确执行。我在哪里弄错了？

Answer 1

正如已经说过的那样，您将复杂性与具体指令的执行次数混淆了。让我们看看这个代码片段。`

#include <iostream>
 #include <vector>
 using namespace std; //don't do this at home
 void exempleFunction(vector<int>& v){ //size of v is n
     for(int i = 0; i < v.size(); i++){
         if (i==0){
             swap(v[0], v[1]);
         }
     }
 }
 int main(){
     int n;
     std::cin>>n;    //n > 1
     vector<int> v(n);
     readVector(n); //gets the values of the vector
     exempleFunction(v);
 }`

在此代码中，exempleFunction（）的成本为O（n），无论o n的值如何，执行交换的次数均为1。话虽如此，让我们看一下这段代码：

``#include <iostream>
  #include <vector>
  using namespace std; //don't do this at home
  void exempleFunction(vector<int>& v){ //size of v is n
      for(int i = 1; i < v.size(); i++){
          swap(v[i], v[i-1]);
      }
  }
  int main(){
      int n;
      std::cin>>n;    //n > 1
      vector<int> v(n);
      readVector(n); //gets the values of the vector
      exempleFunction(v);
  }`` 

在这种情况下，函数swap（）的执行次数是n-1次，比前一种情况多了n-2倍（试想一下，如果n为1000000，那么差异有多大）。但是，exempleFunction的代价仍然是O（n）！代码中发生了同样的事情，该函数的代价并不代表具体方法将执行多少次。函数的成本或复杂性是一种基于n的值来衡量所执行指令数变化的方法。如果用n的大小表示算法执行的指令数，则图形的行为将与算法的成本近似。