C++动态内存分配时间复杂度与分配大小的关系求确认

我之前遇到一个问题：C动态内存分配的时间复杂度如何依赖分配大小？相关讨论没有给出明确结论。我的直觉是更大的内存分配会耗时更久——因为底层分配策略需要寻找更大的连续内存块，这个过程会花费更多时间。我写了一段C程序验证这个猜想，以下是实验结果，希望专业人士确认我的结论和直觉是否正确。

程序输出 #

Total time for size 1048576: 5.50781
Total time for size 2097152: 6.08594
Total time for size 4194304: 6.07031
Total time for size 1048576: 5.48438
Total time for size 2097152: 6.05469
Total time for size 4194304: 6.07031

实验代码 #

#include <ctime>
#include <iostream>

int main()
{
    // Initialize parameters
    int size = 1024*1024;
    int sizes[3] = {size, 2*size, 4*size};
    int nIter = 2000;

    // Repeat the entire experiment twice
    for (int count=0; count<2; count++)
    {
        // Loop though all allocation sizes
        for (int i=0; i<sizeof(sizes)/sizeof(int); i++)
        {
            // Start timer
            const clock_t begin_time = clock();

            // Total of nIter iterations
            for (int j=0; j<nIter; j++)
            {
                // Allocate array
                char *array = new char[sizes[i]];

                // Loop through part of the array
                for (int k=0; k<size; k++)
                    array[k] = 1;

                // Free array
                delete [] array;
            }

            // Report total time
            const float total_time = float(clock()-begin_time)/CLOCKS_PER_SEC;
            std::cout << "Total time for size " << sizes[i] << ": " << total_time << std::endl;
        }
    }
}

专业验证结论 #

你的直觉和实验结果大体正确，但需要补充几个关键细节：

• 内存分配的耗时不能用严格的线性时间复杂度（O(n)）来定义，它的开销和三个核心因素强相关：分配块的大小、内存管理器的实现、当前进程的内存碎片状态。
• 从你的实验数据看：1MB分配耗时约5.5秒，2MB和4MB耗时稳定在6秒左右。这是因为当分配大小超过内存管理器的「小对象阈值」时，分配逻辑会切换——小内存通常用用户态内存池/缓存，耗时接近O(1)；而大内存块会直接向操作系统申请（比如Linux下的mmap、Windows下的VirtualAlloc），这类系统调用的开销更多是固定成本，而非随分配大小线性增长，所以4MB和2MB的耗时差异极小。
• 你的实验中包含了固定的数组写操作（只写前1MB），这部分耗时是恒定的，因此2MB/4MB比1MB多出来的时间，就是内存分配器处理大内存块的额外开销，这也印证了「大分配耗时更长」的直觉。
• 额外补充：如果进程内存碎片严重，寻找大连续空闲块的时间会进一步增加，这时候大分配的耗时可能会有明显波动；而小内存分配因为有缓存池，受碎片影响很小。

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