归并排序时间复杂度计数恒定是否正常？求正确计数实现

嘿，我来帮你把这个问题掰明白！

统计值恒定是否正常？ #

答案是不正常。归并排序的渐近时间复杂度确实是稳定的O(n log n)，但具体的操作次数（尤其是核心的比较次数）会随数组元素的分布变化——比如已完全有序的数组，归并时的比较次数会远少于逆序数组。你现在得到恒定的complexity值，是因为你的计数逻辑根本没统计到这些可变的操作，只统计了和元素顺序无关的固定操作。

你的计数逻辑问题出在哪？ #

看看你的代码，complexity只统计了两类操作：

• 把原数组元素复制到临时数组L/M的次数：每个元素只会被复制一次，总次数固定为数组长度n，和元素顺序完全无关。
• 把临时数组元素移回原数组的次数：每个元素也只会被移动一次，总次数同样固定为n，和元素顺序无关。

而归并排序中唯一会随元素分布变化的核心操作——比较元素的次数，你完全没统计！这就是为什么不管用rand()生成什么元素，最终的complexity值都一模一样。

修正后的准确计数实现方案 #

下面给你两种常用的计数方案，你可以根据需求选择：

方案1：统计所有关键操作（复制+比较+移动） #

这个方案会统计归并过程中的所有核心步骤，结果会随元素分布变化，能真实反映不同输入下的操作量：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DIM 1000000

void merge(int*, int, int, int);
void mergesort(int*, int, int);
int complexity = 0; // 统计所有关键操作的总次数

int main(int argc, char *argv[]){
    int v[DIM], i;
    srand((unsigned)time(NULL)); // 简化time_t的用法，效果一致
    for(i=0; i<DIM; i++){
        v[i] = rand()%100;
    }
    mergesort(v, 0, DIM-1);
    // 大数组建议注释打印排序结果，避免拖慢程序
    // for(i=0; i<DIM; i++) printf("%d\t", v[i]);
    // printf("\n");
    printf("总操作次数: %d\n", complexity);
    return 0;
}

void mergesort(int v[], int lo, int hi){
    int mid;
    if(lo < hi){
        mid = lo + (hi - lo)/2; // 避免lo+hi溢出，比(lo+hi)/2更安全
        mergesort(v, lo, mid);
        mergesort(v, mid+1, hi);
        merge(v, lo, mid, hi);
    }
    return;
}

void merge(int v[], int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int *L = (int*)malloc(n1*sizeof(int));
    int *M = (int*)malloc(n2*sizeof(int));
    int i, j, k;

    // 统计复制到临时数组的操作
    for (i = 0; i < n1; i++){
        L[i] = v[p + i];
        complexity++;
    }
    for (j = 0; j < n2; j++){
        M[j] = v[q + 1 + j];
        complexity++;
    }

    i = 0;
    j = 0;
    k = p;
    while (i < n1 && j < n2) {
        complexity++; // 统计每次比较操作
        if (L[i] <= M[j]) {
            v[k] = L[i];
            i++;
            complexity++; // 统计移动操作
        } else {
            v[k] = M[j];
            j++;
            complexity++; // 统计移动操作
        }
        k++;
    }

    // 统计剩余元素的移动操作
    while (i < n1) {
        v[k] = L[i];
        i++;
        k++;
        complexity++;
    }
    while (j < n2) {
        v[k] = M[j];
        j++;
        k++;
        complexity++;
    }

    free(L); // 必须释放内存，避免内存泄漏
    free(M);
    return;
}

方案2：仅统计比较次数（更贴合时间复杂度的核心） #

如果你只想关注归并排序中最能体现时间复杂度波动的比较次数，可以简化计数逻辑：

// 只需要修改merge函数和初始化complexity的注释
int complexity = 0; // 仅统计比较操作的次数

// ... 其他代码不变 ...

void merge(int v[], int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int *L = (int*)malloc(n1*sizeof(int));
    int *M = (int*)malloc(n2*sizeof(int));
    int i, j, k;

    for (i = 0; i < n1; i++) L[i] = v[p + i];
    for (j = 0; j < n2; j++) M[j] = v[q + 1 + j];

    i = 0;
    j = 0;
    k = p;
    while (i < n1 && j < n2) {
        complexity++; // 仅统计比较次数
        if (L[i] <= M[j]) {
            v[k] = L[i];
            i++;
        } else {
            v[k] = M[j];
            j++;
        }
        k++;
    }

    while (i < n1) { v[k++] = L[i++]; }
    while (j < n2) { v[k++] = M[j++]; }

    free(L);
    free(M);
    return;
}

额外提醒 #

• 你原来的代码没有释放malloc的临时数组，会导致严重的内存泄漏，大数组运行时很可能触发内存溢出，一定要加上free。
• 计算mid时用lo + (hi - lo)/2比(lo+hi)/2更安全，避免lo+hi超出int范围导致溢出。
• 大数组（比如1e6元素）不要打印排序结果，会大幅拖慢程序运行速度。

内容的提问来源于stack exchange，提问作者ProjectEclipse