比较合并和快速排序中的执行时间和时间复杂度

Question

我在教科书中实现了我所学的合并和快速排序，它说每种排序的时间复杂度是这样的：合并排序：O(n.log(n)) / 快速排序：平均 O(n.log(n))和 O(n²) 在最坏的情况下（如果键数组已排序）。

所以我用两种类型的数组执行了程序：排序的和随机的，具有不同的大小。

因为我想得到平均时间，所以每个案例我都尝试了10次。

这里是合并&快速排序的代码：

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

void Merge(vector<int>& s, int low, int mid, int high) {
    int i = low;
    int j = mid + 1;
    int k = low;
    vector<int> u(s);

    while (i <= mid && j <= high) {
        if (s.at(i) < s.at(j)) {
            u.at(k) = s.at(i);
            i++;
        } else {
            u.at(k) = s.at(j);
            j++;
        }
        k++;
    }
    if (i > mid) {
        for (int a = j; a < high + 1; a++) {
            u.at(k) = s.at(a);
            k++;
        }
    } else {
        for (int a = i; a < mid + 1; a++) {
            u.at(k) = s.at(a);
            k++;
        }
    }
    for (int a = low; a < high + 1; a++)
        s.at(a) = u.at(a);
}
void MergeSort(vector<int>& s, int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        MergeSort(s, low, mid);
        MergeSort(s, mid + 1, high);
        Merge(s, low, mid, high);
    }
}

void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}
void Partition(vector<int>& s, int low, int high, int& pvpoint) {
    int j;
    int pvitem;

    pvitem = s.at(low);
    j = low;
    for (int i = low + 1; i <= high; i++) {
        if (s.at(i) < pvitem) {
            j++;
            swap(s.at(i), s.at(j));
        }
        pvpoint = j;
        swap(s.at(low), s.at(pvpoint));
    }
}

void QuickSort(vector<int>& s, int low, int high) {
    int pvpoint;
    if (high > low) {
        Partition(s, low, high, pvpoint);
        QuickSort(s, low, pvpoint - 1);
        QuickSort(s, pvpoint + 1, high);
    }
}

并且这些 main() 函数中的每一个都在 SORTED 和 RANDOM 键数组中打印执行时间。您可以在 Visual Studio(C++):

中添加以下主要函数之一来查看结果

//Sorted key array
int main() {
    int s;
    for (int i = 1; i < 21; i++) { //Size is from 300 to 6000
        s = i * 300;
        vector<int> Arr(s);
        cout << "N : " << s << "\n";

        //Assign Random numbers to each elements
        Arr.front() = rand() % Arr.size();
        for (int j = 1; j < Arr.size(); j++) { Arr.at(j) = ((737 * Arr.at(j - 1) + 149) % (Arr.size() * 5)); }
        sort(Arr.begin(), Arr.end());

        //QuickSort(Arr, 0, Arr.size() - 1);  <- you can switch using this instead of MergeSort(...) below
        for (int i = 0; i < 10; i++) { //print 10 times of execution time
            clock_t start, end;
            start = clock();
            MergeSort(Arr, 0, Arr.size() - 1);
            end = clock() - start;
            printf("%12.3f  ", (double)end * 1000.0 / CLOCKS_PER_SEC);
        }
        cout << endl;
    }
    return 0;
}

//Random key array
int main() {
    int s;
    for (int i = 1; i < 21; i++) {
        s = i * 3000;
        vector<int> Arr(s);
        cout << "N : " << s << "\n";
        for (int i = 0; i < 10; i++) {
            //Assign Random numbers to each elements
            Arr.front() = rand() % Arr.size();
            for (int j = 1; j < Arr.size(); j++) { Arr.at(j) = ((737 * Arr.at(j - 1) + 149) % (Arr.size() * 5)); }

            //QuickSort(Arr, 0, Arr.size() - 1);  <- you can switch using this instead of MergeSort(...) below
            clock_t start, end;
            start = clock();
            MergeSort(Arr, 0, Arr.size() - 1);
            end = clock() - start;
            printf("%12.3f  ", (double)end * 1000.0 / CLOCKS_PER_SEC);
        }
        cout << endl;
    }
    return 0;
}

问题是，结果与他们的时间复杂度不匹配。例如，合并排序（随机数组） 大小 N=3000 打印 20 毫秒，但大小 N=60000 打印 1400~1600 毫秒 !!它应该打印将近 400 毫秒，因为快速排序中的时间复杂度（不是更坏的情况）是 O(n.log(n))，不是吗？我想知道什么影响了这个时间，我怎么才能看到我期望的打印时间。

Answer 1

你在这个问题中发布了相同的代码：而你没有考虑我的回答。

您的 MergeSort 函数有一个缺陷：您在 merge 中复制了整个数组，导致大量开销和二次时间复杂度。这个看似无辜的定义：vector<int> u(s); 将 u 定义为初始化为 s 副本的向量， 完整数组 .

C++ 是一种非常强大的语言，通常过于强大，充满了诸如此类的陷阱。您尝试从算法的已知时间复杂度验证您的程序是否满足预期性能是一件非常好的事情。可惜这种担心太少了。

Answer 2

以下是一些准则：

获取执行时间：

#include <time.h>

int main()
{
  struct timeval stop, start;
  int arr[10000];
  gettimeofday(&start, NULL);
  mergeSort(arr, 0, 9999);
  gettimeofday(&stop, NULL);
  printf("Time taken for Quick sort is: %ld microseconds\n", 
    (stop.tv_sec-start.tv_sec)*1000000+stop.tv_usec-start.tv_usec);
}

比较合并和快速排序中的执行时间和时间复杂度

Comparing Execution time with Time Complexity in Merge & Quick Sort

time-complexity

quicksort

mergesort

execution-time