调用get(Range)相对于范围大小的大O性能是多少?为什么?

问题描述 投票:0回答:1

我想知道范围的方法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;
}
algorithm big-o
1个回答
0
投票

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

© www.soinside.com 2019 - 2024. All rights reserved.