小编Abd*_*sar的帖子

为什么 std::upper_bound() 具有线性复杂度?

我正在阅读 USACO Silver 上有关排序集的指南,我遇到了这个警告sstd::set整数):

警告
假设我们替换s.upper_bound(7)upper_bound(begin(s),end(s),7),这是我们在先决条件模块中用于向量的语法。这仍然会输出预期的结果,但它的时间复杂度与集合的大小是线性的s,而不是对数的,所以一定要避免它!

他们的意思是什么 ?

   upper_bound(s.begin(), s.end(), 7 ); // O(n) ?
   s.upper_bound(7);                    // O(log N) ?
Run Code Online (Sandbox Code Playgroud)

c++ performance binary-search time-complexity upperbound

2
推荐指数
1
解决办法
165
查看次数