Python:检查重叠范围的复杂性

我有两个范围,希望检查它们在Python(v3.5)中是否重叠。以下是一些解决方案。

1a级 :使用集合 intersection 范围:

def overlap_intersection_set(range1, range2):
  return bool(set(range1).intersection(range2))

1b级 :使用集合 十字路口 有两套:

def overlap_intersection_two_sets(range1, range2):
  return bool(set(range1).intersection(set(range2)))

2. :使用 any 和范围 in :

def overlap_any(range1, range2):
  return any([i1 in range2 for i1 in range1])

我一直在试图计算这些方法的成本,主要是在时间方面,但空间复杂性也可能相当大。

这个 Python Wiki page "Time Complexity" 集合交点列表(平均情况):

交叉口s&t(平均情况): O(min(len(s), len(t)) (如果t不是集合,则将“min”替换为“max”)

用于解决方案 1b级 因此,我假设 O(min(len(range1), len(range2)) ,再加上从一个范围创建集的两倍。我认为 bool 功能非常便宜。

用于解决方案 1a级 : O(max(len(range1), len(range2)) ,再加上一次从范围创建集合。

用于解决方案 2. ( 任何 ):我没有找到太多关于复杂性的文档,对于 任何 范围nor 在里面 . 对于后者,我假设范围的行为类似于列表,这意味着 O(n) 对于每个 在里面 调用,从而导致 O(n*m) 具有 n=len(range1) 和 m=len(range2) . 同时 任何 应在找到匹配项后立即指向快捷方式,并且可以避免创建集合。

因此,我的问题涉及算法的复杂性及其Python特定的实现:

1. 将一个范围转换为一个集合的成本有多高?
2. 这个有多贵 bool() 功能真的吗?
3. 做 在里面 对于一个范围,其行为就像列表中的一样( O(n) )?
4. 除了算法复杂性之外,还有哪些其他实现细节相关?
5. 最后,考虑以下问题:检查两个范围之间重叠的最有效方法是什么?

这不容易根据经验进行评估,因为实际计算时间在很大程度上取决于范围的属性,即重叠元素的发现时间及其大小。这就是为什么我在寻找一个更具分析性的解释。