algorithm - 就范围大小而言，调用 get(Range) 的大 O 性能是什么？为什么？

Question

我想知道此代码对于范围的方法 get(Range) 的 Big O 值

我认为它应该是 O(N) N-> 范围值高达 1...N

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;
}

Answer 1

如果 ranges.contains 在 O(f(n)) 中实现，则算法的运行时间为 O(f(n))。因为其他约束将在 O(1) 中检查，并且每个范围在这里由两个整数定义。