为何三角剖分算法最坏情况下时间复杂度为二次？实例存疑

好问题！我当初第一次接触多边形三角剖分的时候，也和你有过一模一样的困惑——毕竟用7个顶点的普通多边形测试，步骤数远小于n²，完全看不出二次复杂度的影子。咱们从最坏情况的实例构造和算法的时间开销细节两个角度来拆解这个问题：

1. 先回顾算法的核心步骤 #

你提到的是一种贪心递归式三角剖分算法，核心逻辑是：

• 选取多边形的最左顶点v
• 尝试找到v的一个非邻接顶点w，使得线段vw是合法对角线（即不与多边形的任何边相交）
• 用vw将原多边形分割成一个三角形和一个更小的子多边形
• 递归处理子多边形，直到所有部分都被剖分成三角形

2. 触发二次复杂度的最坏情况多边形 #

要看到二次时间开销，需要构造一个每次递归只能将问题规模减少1的特殊多边形，并且每次判断对角线合法性都要遍历几乎所有边。最经典的实例是螺旋状凹多边形：

• 设顶点按顺序v₁, v₂, ..., vₙ排列，其中v₁是最左顶点
• 从v₂开始，每个后续顶点都被放置成：v₁与vₖ（k>2）的连线都会穿过多边形内部（不构成合法对角线），只有v₁和相邻的v₂、v₃能形成可切分的三角形
• 比如可以想象这样的形状：v₁在原点，v₂在(1,0)，v₃在(1,1)，v₄在(2,1)，v₅在(2,0)，v₆在(3,0)，v₇在(3,1)...以此类推，形成锯齿状的链，每次切分后剩下的多边形规模只减少1个顶点

3. 二次时间复杂度的推导 #

对于这种特殊多边形，每次递归处理的开销是：

• 第一次处理n顶点多边形：需要遍历O(n)条边，判断v₁与其他顶点的连线是否合法（大部分都不合法），最终只能切出一个三角形，剩下n-1个顶点的同结构多边形
• 第二次处理n-1顶点多边形：需要遍历O(n-1)条边，同样只能切出一个三角形，剩下n-2个顶点的多边形
• ...
• 最后处理3顶点多边形：仅需O(1)次检查

把所有步骤的时间累加起来，总开销就是：
O(n) + O(n-1) + ... + O(1) = O(n²)

你用7个顶点测试时没感受到，是因为7的二次方数值不大，且你大概率用的是普通凸多边形或结构简单的凹多边形——这类场景下算法能快速找到有效对角线，每次分割都能把多边形拆成两个较小的部分，时间复杂度会接近O(n)或O(n log n)，但这是最好/平均情况，不是最坏情况。

总结 #

最坏情况的二次复杂度，本质是因为每次递归只能将问题规模减少1，且每次递归都需要遍历当前规模的所有边进行合法性检查，累加起来就形成了二次的时间开销。只有构造出那种“每次只能切一个小三角形”的特殊多边形，才能触发这种最坏情况。

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