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

好问题！关于realloc的时间复杂度，不能一概而论，得根据内存分配器的实际处理逻辑分两种情况来看：

• 原地扩容（时间复杂度O(1)）
  如果当前动态分配的内存块（也就是你例子里malloc出来的10个int的空间）后面刚好有足够的连续空闲内存，能容纳新增的1个int空间，那么realloc会直接在原内存块的末尾追加空间，不需要复制任何已有元素。这种情况下，操作只需要调整内存块的大小标记，耗时是O(1)。

• 异地扩容（时间复杂度O(n)）
  如果原内存块后面没有足够的连续空间，realloc就会在堆中重新找一块能容纳11个int的新内存区域，然后把原数组里的10个int元素全部复制到新区域，最后释放原来的内存块。这种情况下，耗时和原数组的元素数量n成正比，也就是O(n)（对应你例子里的O(10)）。

关键提示 #

到底会触发哪种情况，完全由当前堆的内存布局决定，这是C标准库的内存分配器（比如glibc的ptmalloc）负责管理的，我们在代码里没法提前预判。所以从编程的严谨性和最坏情况分析的角度，我们通常认为realloc的时间复杂度是O(n)——因为你不能依赖“刚好有空闲空间”这个不确定的条件。

另外补充一个小知识点：如果是按倍数扩容（比如每次把数组大小扩为原来的2倍），那么多次realloc的均摊时间复杂度会是O(1)；但像你例子里这样每次固定加1的扩容方式，多次操作的均摊复杂度还是O(n)，因为大概率每次都需要复制整个数组。

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