每日科普 · 2026-09-17 周四

考研 408 × 求职面试

知识点 · 数据结构 · 进阶

顺序表的动态扩容与均摊复杂度

顺序表用一段连续内存存数据，并记录长度和容量。当元素个数等于容量时再插入，就要扩容：申请一块更大的连续空间（常见做法是容量翻倍），把旧数据整体搬过去，再释放旧空间。

关键在于「均摊复杂度」。单次插入若触发扩容，需要搬运 n 个元素，代价是 O(n)，看起来插入很慢。但扩容后容量翻倍，要再插入 n/2 次才会再次扩容。把一次 O(n) 的搬运分摊到随后多次插入上，平均每次插入仍只有 O(1)。这就是均摊（摊还）分析：不否认某一次很慢，但保证连续 m 次操作的总代价是 O(m)。

1. 顺序表的随机访问是 O(1)，与扩容无关。
2. 若每次只增加固定容量（如 +1），则几乎每次插入都要搬，总代价 O(n²)，必须采用倍增策略。
3. 代价是扩容瞬间的停顿与部分空间浪费。

每日一题 · 数据结构

顺序表的动态扩容与均摊复杂度

一个初始容量为 1 的动态顺序表，采用容量翻倍策略，连续执行 n 次尾插操作（不计空间浪费），这 n 次操作的总元素搬运次数约为多少？
A. n		B. n·log n		C. 2n		D. n²

解析

选 C。容量按 1→2→4→…→2^k 翻倍，每次扩容要搬运当时的全部元素，总搬运量 = 1+2+4+…+2^k，其中 2^k < n ≤ 2^(k+1)，等比数列求和约为 2n，故总代价 O(n)，均摊到每次插入约 2 次搬运，即 O(1)。A 错在遗漏了每次翻倍前的历史搬运；B、D 高估了代价，因为扩容不会每次插入都发生。

面试小贴士 · 数据结构

顺序表的动态扩容与均摊复杂度

面试官常问「动态数组尾插为什么是 O(1)」。答：单次最坏 O(n)，但倍增扩容下总代价等比求和约为 2n，均摊 O(1)。易错点：把均摊当成最坏情况、答成「每次都 O(n)」、忽略倍增与定长增量的区别，以及忘记提到扩容停顿和空间浪费。

代码实现 · C

代码示例

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

typedef struct {
    int *data;
    int size;      /* 当前元素个数 */
    int capacity;  /* 当前容量 */
} SeqList;

/* 扩容：容量翻倍，均摊 O(1) */
static void grow(SeqList *L) {
    int newCap = L->capacity ? L->capacity * 2 : 1;
    int *p = (int *)realloc(L->data, newCap * sizeof(int));
    if (!p) { printf("内存不足\n"); exit(1); }
    L->data = p;
    L->capacity = newCap;
}

/* 尾插 */
void push_back(SeqList *L, int x) {
    if (L->size == L->capacity) grow(L);
    L->data[L->size++] = x;
}

int main(void) {
    SeqList L = {NULL, 0, 0};   /* 空表，容量为 0 */
    for (int i = 0; i < 12; i++) {
        push_back(&L, i);
        printf("插入 %2d: size=%2d capacity=%2d\n", i, L.size, L.capacity);
    }
    free(L.data);
    return 0;
}