圆周上多角度区间逐次求交算法的时间复杂度分析

首先明确前提：我们讨论的角度区间是模360°圆周上的连续弧段，所有输入的单个区间无论起止角度数值多大，本质都是圆周上1段连通的弧（若区间覆盖角度范围≥360°，等价于覆盖整个圆周，求交时可以直接忽略）。

区间数量不会出现指数级增长 #

你担心的区间数涨到2ⁿ量级的情况完全不可能发生，核心逻辑非常直接：

• 圆周上任意个连续弧的交集，一定是若干段互不相交的连续弧组成的集合，这些弧之间的空隙，就是所有输入区间没有覆盖到的补集范围。
• 对任意一个输入的连续区间，它没覆盖到的补集部分，在圆周上有且仅有1段连续的空隙——你可以直观想象：圆上画一段连续的弧，剩下没被画到的部分必然也是连在一起的一整段。
• 逐次迭代求交的过程，本质就是不断往圆周上新增补集空隙的过程：
  • 处理第1个区间时，交集只有1段弧，对应1个补集空隙；
  • 每处理1个新输入区间，相当于新增1段连续的补集空隙。这段新空隙最多只会落在当前已有的某一段交集中，把这一段交集劈成2段，也就是总区间数最多+1；如果新空隙和之前已有的空隙重叠，总区间数不会增加，甚至可能因为空隙合并而减少。
• 你提到的两个区间求交输出2个结果的情况，本质就是第二个区间的补集空隙刚好落在第一个区间的覆盖范围内，把原来的1段交集劈成了2段，区间数只从1涨到2，没有翻倍。
• 处理完n个输入区间时，交集的区间总数量上界就是n，连超线性增长都不会出现，更不可能有O(2ⁿ)的指数级膨胀。

逐次迭代算法的时间复杂度 #

基于上面的结论，时间复杂度可以直接推导：

• 处理第k个输入区间时，当前存储的交集区间数量最多是k-1段；
• 每一段当前区间和新输入的单个连续区间做求交，都是常数时间O(1)的操作：只需要比较角度范围判断重叠部分即可，哪怕新输入区间跨0点，最多拆成2段线性范围做比较，依然是常数耗时；
• 因此处理第k个区间的耗时是O(k)，把所有步骤的耗时加总：1+2+3+…+(n-1) = n(n-1)/2，总时间复杂度是O(n²)。

补充：如果追求更高性能，可以替换逐次迭代思路：把所有输入区间的补集空隙的起止角度做归一化后排序，一次遍历圆周就能算出所有交集，时间复杂度可以降到O(n log n)，属于另外的实现方案。

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