我想知道范围的方法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;
}
如果在ranges.contains
中实现O(f(n))
,则算法的运行时间为O(f(n))
。因为其他约束将在O(1)
中检查,并且每个范围在此处由两个整数来定义。