C中realloc函数的时间复杂度是多少？

Question

我有一个问题:realloc函数的时间复杂度是多少？例如,我有一个整数数组:a [10].当然,数组已经以这种方式动态分配=>

int *a = (int*)malloc(10*sizeof(int));

然后我想将这个数组的大小调整为11,以便为数组a插入一个额外的值,所以我做=>

a = (int*)realloc(a, 11*sizeof(int));

我的问题是:重新分配的时间复杂度是多少？realloc是否只是在数组中添加一个额外的单元格,然后它需要O(1)或者它重新占用整个数组a,添加额外的第11个单元格并返回新大小的数组,在这种情况下,此操作的时间复杂度为O (N)？哪种假设是正确的？

Answer 1

首先,您的代码(以问题的原始形式)是错误的.它至少应该是

a = realloc(a, 11*sizeof(int));

(否则你可能有未定义的行为,通常情况下sizeof(int)大于1).BTW realloc不应该用C铸造.

然后,你的问题

C中realloc函数的时间复杂度是多少？

没有任何意义,除非你谈到一些特殊的 realloc函数,你知道它的实现.

请注意,realloc允许失败.这是一个有效但无用且持续时间的实现(参见这个答案;它符合标准符合realloc标准n1570的字母,但不符合标准):

void *realloc( void *ptr, size_t new_size ) { 
  errno = ENOMEM;
  return NULL;
}

最后,在实践中,您可以考虑malloc并realloc以某种方式进行昂贵的操作(典型的运行时可能是几微秒,因此比添加时间慢几千倍),并且在许多情况下您不希望realloc每次循环.所以你宁愿使用一些几何增长realloc(比如这里)

realloc是否只是在数组中添加一个额外的单元格,然后它需要O(1)或者它重新占用整个数组a,添加额外的第11个单元格并返回新大小的数组,在这种情况下,此操作的时间复杂度为O (N)？

两者都可能发生.您可以想象malloc保持分配大小的某个位置(由实现向上舍入...)并且在良好情况下realloc返回相同的指针(因此O(1))并且在不太乐意的情况下需要将内存区域复制到其他地方.不知道您的具体实现(的malloc,realloc,free),你可以不知道什么是最常见的情况,或者它们的概率分布.顺便说一句,好像是一个realloc 其执行始终将数据复制(或失败)是符合标准的(但效率不高).如果您需要了解更多信息,则应进行基准测试.

最后,许多实现C标准库是免费软件(如GNU libc中,MUSL-libc的,...),你可能会研究他们的源代码malloc,free,realloc(以上操作系统原语-通常的系统调用 -越来越多的虚拟地址空间 ;在Linux上,类似的mmap(2) )