如何在排序问题中同时满足时间复杂度和空间复杂度？

Question

我正在尝试使用冒泡排序算法对数字进行升序排序。但是，我仍然收到 OufOfMemory 错误。

如何确保我的代码中不会出现 OufOfMemory 错误？

问题就像下面的句子。

• 8MB内存容量有限制

• 有5秒的时间限制。

• 第一行给出数字的个数N（1≤N≤10,000,000）

• 从第二行开始在 N 行中给出数字。这个数是小于等于10000的自然数。

  https://www.acmicpc.net/problem/10989

这是我尝试打印数字的代码。

#include <stdio.h>
#include <stdlib.h>

void swap(int* x, int* y){
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

int main(){

    int N, i, j;
    scanf("%d", &N);

    int* arr;
    arr = (int*)malloc(N * sizeof(int));

    for(i=0;i<N;i++){
        scanf("%d", &arr[i]);
    }
    
    int min_value = arr[0];
    for(i=0;i<N;i++){
        for(j=0;j<N-i-1;j++){
            if(arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
            }
        }
    }

    for(i=0;i<N;i++){
        printf("%d\n", arr[i]);
    }

    return 0;
}

#include <stdio.h>
#include <stdlib.h>

void swap(int* x, int* y){
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

int main(){

    int N;
    int i, j;
    scanf("%d", &N);

    long* arr;
    arr = (long*)malloc(N * sizeof(int));

    for(i=0;i<N;i++){
        scanf("%ld", &arr[i]);
    }

    for(i=0;i<N;i++){
        for(j=0;j<N-i-1;j++){
            if(arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
            }
        }
    }

    for(i=0;i<N;i++){
        printf("%ld\n", arr[i]);
    }

    return 0;
}

当我猜测内存不足的原因时，似乎内存超出是由动态分配中的 N * sizeof(int) 引起的。如果 N 的取值范围最大为 10,000,000，最坏的情况是 N * int 为 2.097.152。结果超出了记忆。

另外，我像下面这句话一样计算了8MB的内存。

8 * 1024 * 1024 / 4 = 2.097.152

这是想要的结果：

• 满足5秒的时间限制
• 满足8MB的内存限制

这个和我的问题有关，但是没有解决我的问题

感谢您阅读我的帖子。

Answer 1

int

可能比存储 0..10,000 中的数字所需的更大。这其实很有可能。您可以使用

int16_t

或

uint16_t

。但是这些数组仍然会占用 20 MB 或超过 19 MiB。这意味着您不可能一次将所有数字放入内存中。

这排除了冒泡排序。事实上，这排除了所有常规类型（因为您可能也不能使用外部存储）。

但是由于我们要对小数进行排序，我们可以使用非常规的排序方法，例如 计数排序。我们需要一个包含 10,001 个

uint32_t

对象的数组，也就是说刚好超过 40 KB 或不到 40 KiB。这远低于您的限制。

---

在时间方面，冒泡排序效率极低，对于您的目标来说可能不够快。

计数排序不会有任何时间问题。