Java 数据结构的时间复杂度实验：从 AList 扩容到 SLList 遍历

背景

时间复杂度是算法分析的核心概念，但仅从公式推导往往缺乏直观感受。本文通过两个实验，用实际耗时数据验证不同实现方式的性能差异：

AList 的 resize 策略——动态数组在扩容时，累加式与成倍式策略如何影响 addLast 的均摊复杂度？
SLList 的 getLast 方法——单向链表访问尾部元素为何是 $O(n)$ ？

实验一：AList 的 resize 策略

实现

在基于数组的动态列表中，当底层数组容量已满时，需要调用 resize 分配更大的空间并拷贝已有元素。以下为 AList 的最小实现：

public class AList<Item> {
    private Item[] items;
    private int size;

    public AList() {
        items = (Item[]) new Object[100];
        size = 0;
    }

    private void resize(int capacity) {
        Item[] a = (Item[]) new Object[capacity];
        System.arraycopy(items, 0, a, 0, size);
        items = a;
    }

    public void addLast(Item x) {
        if (size == items.length) {
            resize(size + 1);  // ← 在此替换不同的扩容策略
        }
        items[size] = x;
        size = size + 1;
    }
}

测试方法

逐步倍增 $N$ 值，记录连续添加 $N$ 个元素的总耗时，再除以操作次数得到每次操作的平均耗时：

public static void timeAListConstruction() {
    java.util.ArrayList<Integer> Ns = new java.util.ArrayList<>();
    java.util.ArrayList<Double> times = new java.util.ArrayList<>();
    java.util.ArrayList<Integer> opCounts = new java.util.ArrayList<>();
    Ns.add(1000);
    for (int i = 0; i < 8; i++) {
        AList<Integer> test = new AList<>();
        int curOpCounts = 0;
        Stopwatch sw = new Stopwatch();
        for (int n = 0; n < Ns.get(Ns.size() - 1); n++) {
            test.addLast(0);
            curOpCounts++;
        }
        times.add(sw.elapsedTime());
        Ns.add(Ns.get(Ns.size() - 1) * 2);
        opCounts.add(curOpCounts);
    }
    Ns.remove(Ns.size() - 1);
    printTimingTable(Ns, times, opCounts);
}

实验结果

累加式扩容

每次 +1：

N	time (s)	# ops	microsec/op
1,000	0.00	1,000	1.00
2,000	0.00	2,000	1.00
4,000	0.01	4,000	2.50
8,000	0.03	8,000	3.13
16,000	0.08	16,000	5.00
32,000	0.31	32,000	9.63
64,000	1.02	64,000	15.92
128,000	3.15	128,000	24.64

每次 +10：

N	time (s)	# ops	microsec/op
1,000	0.00	1,000	0.00
2,000	0.00	2,000	0.00
4,000	0.00	4,000	0.75
8,000	0.00	8,000	0.50
16,000	0.01	16,000	0.81
32,000	0.05	32,000	1.69
64,000	0.15	64,000	2.30
128,000	0.46	128,000	3.60

成倍扩容

每次 ×2：

N	# ops	microsec/op
1,000	1,000	0.00
2,000	2,000	1.00
4,000	4,000	0.00
8,000	8,000	0.13
16,000	16,000	0.06
32,000	32,000	0.06
64,000	64,000	0.05
128,000	128,000	0.01

每次 ×3：

N	# ops	microsec/op
1,000	1,000	1.00
2,000	2,000	0.00
4,000	4,000	0.25
8,000	8,000	0.00
16,000	16,000	0.19
32,000	32,000	0.09
64,000	64,000	0.03
128,000	128,000	0.02

直观对比

$N = 128000$ 时各策略的每次操作耗时（µs/op）：

+1 24.64 µs/op

+10 3.60 µs/op

×3 0.02 µs/op

×2 0.01 µs/op

分析

成倍扩容的效率远高于累加式扩容。 每次 +1 的策略在 $N = 128000$ 时每次操作耗时约 24.64 µs，而 ×2 策略仅需 0.01 µs，差距超过 2000 倍。
累加式扩容的均摊复杂度为 $O(n)$ ：每次扩容只多出常数个空位，导致频繁触发 resize，而每次 resize 都需要拷贝整个数组。连续 $N$ 次 addLast 的总拷贝量为 $O(N^2)$ ，均摊到每次操作即 $O(N)$ 。
成倍扩容的均摊复杂度为 $O(1)$ ：以 ×2 为例，扩容发生的频率呈指数递减——在第 $1, 2, 4, 8, \ldots, 2^k$ 次插入时触发。总拷贝量为 $1 + 2 + 4 + \cdots + 2^k < 2N$ ，均摊每次操作仅常数时间。
×2 与 ×3 的细微差异： 两者均为 $O(1)$ 均摊，但在本实验中 ×2 略优于 ×3。这可能与 ×3 更频繁地「浪费」空间有关——更大的扩容步长意味着更少的 resize 调用，但每次拷贝的元素更多，且内存分配的粒度更大，可能影响缓存命中率。不过差异量级极小，在实际应用中通常可以忽略。

实验二：SLList 的 getLast 方法

实现

单向链表（SLList）通过节点指针串联元素。以下为最小实现，使用 Sentinel 节点简化边界处理：

public class SLList<Item> {
    private class IntNode {
        public Item item;
        public IntNode next;
        public IntNode(Item i, IntNode n) { item = i; next = n; }
    }

    private IntNode sentinel;
    private int size;

    public SLList() {
        sentinel = new IntNode(null, null);
        size = 0;
    }

    public void addLast(Item x) {
        IntNode p = sentinel;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new IntNode(x, null);
        size++;
    }

    public Item getLast() {
        IntNode p = sentinel;
        while (p.next != null) {
            p = p.next;
        }
        return p.item;
    }
}

getLast 的实现与 addLast 类似：必须从头遍历到链表末尾，时间复杂度为 $O(n)$ 。

测试方法

固定每次调用 getLast 10000 次，逐步倍增链表规模 $N$ ，观察耗时变化：

public static void timeGetLast() {
    java.util.ArrayList<Integer> Ns = new java.util.ArrayList<>();
    java.util.ArrayList<Double> times = new java.util.ArrayList<>();
    java.util.ArrayList<Integer> opCounts = new java.util.ArrayList<>();
    SLList<Integer> test = new SLList<>();
    Ns.add(1000);
    for (int i = 0; i < 8; i++) {
        for (int n = 0; n < Ns.get(Ns.size() - 1) / 2; n++) {
            test.addLast(0);
        }
        int curOpCounts = 0;
        Stopwatch sw = new Stopwatch();
        for (int j = 0; j < 10000; j++) {
            test.getLast();
            curOpCounts++;
        }
        times.add(sw.elapsedTime());
        Ns.add(Ns.get(Ns.size() - 1) * 2);
        opCounts.add(curOpCounts);
    }
    Ns.remove(Ns.size() - 1);
    printTimingTable(Ns, times, opCounts);
}

踩坑记录： 最初的测试代码与 AList 实验相同——每轮循环单独创建新的 SLList。但由于 SLList 的 addLast 本身是 $O(n)$ ，每轮重建 $N$ 个节点的链表需要 $O(N^2)$ 时间，导致测试极慢。修正方式是将 test 列表移出循环，每轮仅做增量 addLast。

实验结果

N	time (s)	# ops	microsec/op
1,000	0.01	10,000	0.90
2,000	0.02	10,000	1.90
4,000	0.05	10,000	4.50
8,000	0.10	10,000	9.90
16,000	0.20	10,000	20.30
32,000	0.38	10,000	37.50
64,000	0.80	10,000	79.80
128,000	1.62	10,000	162.30

直观对比

128,000 162.30 µs/op

64,000 79.80 µs/op

32,000 37.50 µs/op

16,000 20.30 µs/op

8,000 9.90 µs/op

4,000 4.50 µs/op

2,000 1.90 µs/op

1,000 0.90 µs/op

分析

耗时与 $N$ 严格成正比—— $N$ 每翻倍，耗时也近乎翻倍，这正是 $O(n)$ 的典型特征。getLast 每次调用都需要从头遍历到链表末尾，链表越长，遍历的节点越多。

值得注意的是，链表的 getLast 是 $O(n)$ ，而 AList 的 getLast（即 items[size - 1]）是 $O(1)$ 。数组支持随机访问，可以直接通过下标定位最后一个元素；而链表只能沿指针顺序遍历，无法跳过中间节点。

如果需要频繁访问尾部元素，可以在 SLList 中额外维护一个指向尾节点的指针（tail pointer），将 getLast 优化为 $O(1)$ ——但代价是 addLast 和其他操作需要同步维护该指针。

总结

	AList addLast	SLList getLast
影响因素	扩容策略	链表结构
差的实现	每次 +1 → 均摊 $O(n)$	无尾指针 → $O(n)$
好的实现	每次 ×2 → 均摊 $O(1)$	维护尾指针 → $O(1)$
核心原理	避免频繁拷贝整个数组	避免遍历整个链表

两个实验殊途同归：时间复杂度的差异在小数据规模下可能被忽略，但在数据量增大时会带来数量级的性能差距。 选择合适的数据结构和实现策略，是写出高效代码的基础。

在实际工程中，Java 的 ArrayList、Python 的 list 等标准库均采用成倍扩容策略；而需要频繁访问尾部的场景，双向链表（如 Java 的 LinkedList）或带尾指针的实现会是更好的选择。