邻接表空间复杂度为何是Θ(m + n)？兼论Θ(m*log₂n)的疑问

一、为什么邻接表的空间复杂度是Θ(m+n) #

邻接表的核心结构是「每个节点对应一个存储其邻接节点的容器」，空间消耗分为两部分：

• 节点表头开销：不管节点有没有邻接边，都需要为每个节点分配一个表头（比如指向容器的指针），这部分空间是Θ(n)（n为节点总数）。
• 边的存储开销：每条边会被记录在其关联节点的容器中——无向图中每条边会存两次（比如边a-b会同时出现在a和b的邻接表），有向图中每条边只存一次。总共有m条边，这部分空间是Θ(m)。

把两部分加起来，总空间复杂度就是Θ(m+n)。

用你的例子验证 #

你给出的图：n=5（a、b、c、d、e），m=7（a-b、a-c、a-d、b-e、c-d、c-e、e-a）。

• 节点表头：5个，占Θ(5)空间；
• 边的存储：a的邻接表存3个节点，b存1个，c存2个，d存0个，e存1个，总共3+1+2+0+1=7个条目，刚好对应m=7，占Θ(7)空间。
  总空间为5+7=12，完全符合Θ(m+n)的量级。

解决完全图的矛盾疑问 #

你提到当边数m=C(n,2)=n(n-1)/2（无向完全图）时，邻接表总存储量是n + 2m =n +n(n-1)=n²，看似和Θ(m+n)不符？这是对渐近复杂度的误解：
当n很大时，m=n(n-1)/2是Θ(n²)，而m+n =n(n-1)/2 +n =n(n+1)/2，同样是Θ(n²)——n²和n(n+1)/2是同阶的，因为它们的比值趋近于常数2。所以存在常数c2=2，使得n² ≤2(m+n)，完全满足Θ(m+n)的定义（存在常数c1、c2，让c1*(m+n)≤总空间≤c2*(m+n)）。

二、教授提到的Θ(m*log₂n)是什么场景 #

这个复杂度通常对应邻接表用平衡二叉搜索树（如红黑树）或有序结构存储邻接节点的情况：

• 普通邻接表用链表/动态数组存储邻接节点，每个边条目只需要Θ(1)空间（比如一个节点指针或索引）；
• 如果为了支持快速查找邻接节点（比如判断两个节点是否相连），改用平衡二叉搜索树存储，每个树节点除了存储邻接节点信息，还需要维护树的结构（如左右子节点指针、颜色标记等）。此时每个边对应的存储项空间开销是Θ(logn)（因为树的高度是O(logk)，k是节点的邻接数，最坏情况下k=n-1，高度为O(logn)）；
• 总空间变为：节点表头的Θ(nlogn)（每个表头对应一棵平衡树的根节点） + 边的Θ(mlogn)。当m远大于n时（比如稠密图），总空间就近似为Θ(m*logn)。

另外一种可能是按比特位计算指针空间：在64位系统中，一个指针占8字节（64位，即log₂(2^{64)=64位），也就是Θ(logn)的空间（因为n最多为2}64）。此时每个表头指针和每个边的指针都占Θ(logn)空间，总空间就是(n +m)logn，当m远大于n时，就是Θ(mlogn)。

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