问题标签 [lower-bound]

给定具有 n 个元素 [1,...,n] 的数组的最大元素 M，每个基于比较的排序算法的时间复杂度下限 Ω(nlogn) 如何受到影响？我必须强调给出了数组的最大元素 M。

在 Java 中是否有其他替代方法可以实现相同的功能？在 C++ 中，我可以使用这些奇妙的方法，让我的生活更轻松。Java也可以吗？我的唯一目标是编写简单、干净且不易出错的代码。

我想知道 C# 是否与 Java 的<X super MySubClass>通用约束等效。

要指定上限，可以使用class Foo<T> where T : MySuperClass { ... }，但我们如何指定泛型参数的下限？

有一些方法可以获得类似的结果，但我还没有找到完美的东西：

1. 使用第二个通用参数——但调用者可以指定实际下限的子类。

   /li>

2. 这有时用于扩展方法，因此扩展方法的参数U被限制为类参数的超类T。

   /li>

3. 在接口上使用方差，但我不确定这是否可以用来指定泛型参数的下限。

正是问题所问的。这是我明天的期中考试问题，我似乎无法在网上或我的教科书中找到答案。谢谢您的帮助！！

我知道你永远不应该使用std::find(some_map.begin(), some_map.end())or std::lower_bound，因为它会花费线性时间而不是some_map.lower_bound. 类似的事情发生在std::list: 有std::list::sort排序功能，但你无法调用std::sort(some_list.begin(), some_list.end())，因为迭代器不是随机访问的。

但是，std::swap例如，标准容器具有重载，因此调用swap(some_map, other_map)需要 O(1)，而不是 O(n)。为什么 C++ 标准没有为我们提供地图和集合的专用版本lower_bound和？find有深层次的原因吗？

我有一个排序向量数组，

向量<int> b[1000009]；

现在我必须在 b[factor] 行中搜索 x 和 y 之间的范围。
'factor'、'x' 和 'y' 都是整数。
我使用了以下方法：

但是这种方法并不是一直都给出正确的答案。除此之外，我还想使用一些比较器功能来实现相同的目的。这是我第一次使用lower_bound()和upper_bound()。所以请告诉我如何在这里实现比较器功能。

我正在尝试使用这些函数找到我的向量（可能的向量）的上限和下限。结构数据包含 3 个字符串，我使用字符串日期进行比较。

但是这样做，编译器会显示以下消息：

使用这些功能的正确方法是什么？

我目前正在研究旅行推销员问题，并且想知道是否有人能够简单地解释持有的 karp 下限。我一直在看很多论文，我很难理解它。如果有人可以简单地解释一下，那就太好了。

我也知道有一种方法可以计算不包括起始顶点的顶点的最小生成树，然后从起始顶点添加两个最小边。

在scala 规范中，有一些关于方差和下限的描述：

类型声明或类型参数的下限的方差位置与类型声明或参数的方差位置相反。

在第 44 页。

我可以得到一些想法，但我无法清楚地解释它。你能给我一些详细的解释吗？

STL provides binary search functions std::lower_bound and std::upper_bound, but I tend not to use them because I've been unable to remember what they do, because their contracts seem completely mystifying to me.

Just from looking at the names, I'd guess that "lower_bound" might be short for "last lower bound",
i.e. the last element in the sorted list that is <= the given val (if any).
And similarly I'd guess "upper_bound" might be short for "first upper bound",
i.e. the first element in the sorted list that is >= the given val (if any).

But the documentation says they do something rather different from that-- something that seems to be a mixture of backwards and random, to me. To paraphrase the doc:
- lower_bound finds the first element that's >= val
- upper_bound finds the first element that's > val

So lower_bound doesn't find a lower bound at all; it finds the first upper bound!? And upper_bound finds the first strict upper bound.

Does this make any sense?? How do you remember it?