关于get(Range)方法的大O时间复杂度及代码分析问询

架构老林

2026-5-12

嘿，咱们来把这个问题掰扯清楚——你的疑问核心其实落在ranges集合的底层实现上，这直接决定了get(Range)方法的时间复杂度！

问题1：`get(Range)`的时间复杂度（相对于ranges规模）

时间复杂度分两种核心情况：

若ranges是支持对数时间查找的有序集合（比如Java里的TreeSet、基于平衡二叉树/跳表实现的有序容器）：整体复杂度是 O(log N)，N为ranges的元素总数。
若ranges是无序集合（比如普通ArrayList、未排序的链表）：整体复杂度是 O(N)。

问题2：针对你贴出的代码分析时间复杂度

先看你给出的代码：

Range get(Range r) {
    Range lower = ranges.lower(r);
    Range higher = ranges.higher(r);
    if (ranges.contains(r)) {
        return r;
    }
    if (lower != null && lower.end >= r.start) {
        return lower;
    }
    if (higher != null && higher.start <= r.end) {
        return higher;
    }
    return null;
}

代码里的关键操作是lower()、higher()、contains()这三个方法，它们的复杂度直接决定了整个get方法的开销：

如果ranges是有序集合：
这类集合的lower()、higher()、contains()都是基于二叉搜索实现的，平衡二叉树的高度是log N，所以每个操作的时间都是O(log N)。
整个方法里就是三次O(log N)的查找，再加上几个常数时间的判断逻辑，所以整体复杂度是 O(log N)——这也是这类场景下最常见的情况，毕竟用lower/higher这类方法的初衷就是为了高效范围查找。
如果ranges是无序集合：
要找到比r小的最大元素（lower）或比r大的最小元素（higher），必须遍历整个集合的所有元素；contains()方法也需要遍历全集合（除非是哈希集合，但哈希集合没法高效做范围查找）。这种情况下，lower和higher的操作都是O(N)，所以整体复杂度是 O(N)。