问题标签 [lower-bound]

我写了一个以 O(n) 排序的简单程序。它的内存效率非常低，但这不是重点。

它使用 a 背后的原理HashMap进行排序：

那么这算不算一种 O(n)，即使它以一种时髦的格式返回结果？

C++ 草案提到了 std::lower_bound：

请注意，这允许（通过暗示）比较不同（但可比较）的类型而不是*ForwardIterator返回的类型，但对迭代器改进的数​​量没有复杂性限制。（对于基于节点的容器，这将是 O(last − first) 迭代器改进。）

该标准没有详细说明这些函数，但暗示这些函数用于 O(log2(last − first)) 比较和改进，但要求搜索键与包含的类型相同。

所以我的问题是：
（1）有没有办法获得std::set::lower_bound搜索类型的速度和灵活性std::lower_bound？
(2) 为什么std::lower_bound不需要专门化std::set::iterator？
(3) 是否有std::lower_bound 专门针对 的实现std::set::iterator，或者是否有理由不这样做？

我希望能找到类似的东西：

或者：

但我怀疑它的存在。显然，所有这些都可以扩展到其他基于树的容器和其他算法。我会自己编写代码，但这需要我使用特定于实现的代码。这个想法来自这个问题：Efective search in set with non-key type

我在scala中遇到了一些继承和下限问题；我将尝试用一个例子来解释它：我有一个类 Person ，其签名如下：

我还创建了一个子类 Worker，他的方法 doSomething 如下所示：

然而，这会引发一个错误，指出 Worker.doSomething() 没有覆盖任何东西？

在 Scott Meyers 的有效 STL 中（第 195 页）有以下行：

“必须测试 lower_bound 的结果以查看它是否指向您要查找的值。与 find 不同，您不能仅针对 end 迭代器测试 lower_bound 的返回值。”

谁能解释为什么你不能这样做？似乎对我来说很好。

众所周知，任何基于比较模型的排序算法都有nlogn的下界，即Omega(nlogn)。这可以在数学上证明。

但众所周知，荷兰国旗问题可以在 O(n) 时间内对 3 个不同的元素（重复使用）进行排序。它也是基于比较模型，但可以在 O(n) 时间内排序。那么我们如何证明基于比较模型的排序下限是合理的，因为荷兰国旗问题有点违反了这一点。

请帮助我理解其中的区别......

谢谢

有人可以向我解释这个问题的解决方案吗？

假设给定一个包含n 个元素的序列进行排序。输入序列由n=k个子序列组成，每个子序列包含k个元素。给定子序列中的元素都小于后续子序列中的元素并且大于前面子序列中的元素。因此，对长度为n的整个序列进行排序所需的只是对n=k个子序列中的每个子序列中的k个元素进行排序 。显示解决该排序问题变体所需的比较次数的n lg k下限。

解决方案：

令S是一个由n 个元素组成的序列，分为n/k个子序列，每个子序列的长度为k ，其中任何子序列中的所有元素都大于前一个子序列的所有元素并且小于后续子序列的所有元素。

宣称

在最坏的情况下，对S进行排序的任何基于比较的排序算法都必须花费(n lg k)时间。

证明

首先请注意，正如提示中所指出的，我们不能通过将下限相乘来对每个子序列进行排序来证明下限。那只会证明没有更快的算法可以独立地对子序列进行排序。这不是我们被要求证明的；我们不能引入任何额外的假设。

现在，考虑 S 的任何比较排序的高度为 h 的决策树。由于每个子序列的元素可以按任何顺序排列，因此k! 排列对应于子序列的最终排序顺序。并且，由于有n/k 个这样的子序列，每个子序列都可以按任何顺序排列，因此 S 的(k!)^n/k个排列可能对应于某些输入顺序的排序。因此，任何对 S 进行排序的决策树必须至少有(k!)^n/k 个叶子。由于高度为h的二叉树的叶子 不超过2^h，我们必须有2^h ≥ (k!)^(n/k)或h ≥ lg((k!)^n/k)。因此我们得到

第三行来自k! 其k/2 个最大项每个至少为k/2。（我们在这里隐含地假设 k 是偶数。如果k是奇数，我们可以调整地板和天花板。）

由于在任何决策树中至少存在一条对长度至少为(n/2) lg(k/2)的 S 进行排序的路径，因此任何基于比较的 S 排序算法的最坏情况运行时间为(n lg ķ）。

有人可以指导我完成代码块中的步骤吗？尤其是lg k! 变为lg((k/2)^k/2)。

我在 C++ 中遇到了以下代码片段（我还没有使用 C++11）：

特别是，我不喜欢最后的使用，也不喜欢to--itr的比较，它们都让我觉得不对劲。itrbegin()

我想知道 STL 是否有办法进行某种查找，如果未找到将返回 end() （或 rend()），否则返回小于或等于的最后一个元素value所以代码看起来更像这样：

从某种意义上说，我想要一个 reverse_lower_bound()，它返回一个反向迭代器到最后一个不大于的元素，value或者如果没有找到 rend()。

是否有使用二分搜索的函数，例如根据给定谓词lower_bound返回最后一项小于或等于的项？

lower_bound定义为：

查找值大于或等于指定值的有序范围中的第一个元素的位置，其中排序标准可以由二元谓词指定。

和upper_bound：

查找值大于指定值的有序范围中的第一个元素的位置，其中排序标准可以由二元谓词指定。

具体来说，我有一个按时间排序的事件容器，并且在给定时间内，我想找到在该点之前或该点出现的最后一个项目。我可以通过上/下界、反向迭代器和使用std::greateror的某种组合来实现这一点std::greater_equal吗？

编辑：如果您在数组开始之前要求一个点，则需要对 user763305 的建议进行调整：

我正在阅读此页面http://www.scala-lang.org/node/137，我了解协方差和下限是什么，但不清楚的是这一行：

不幸的是，该程序无法编译，因为只有在类型变量仅在协变位置使用时才能使用协方差注释。由于类型变量 T 显示为方法前置的参数类型，因此该规则被打破。

为什么elem必须是 的超类型的实例T，如果ListNode已经是协变的，为什么elem不能添加到当前列表中。

我想做以下事情：

也就是说，给定一个 的不可变列表T，您可以将任何添加U到列表中以生成一个 的不可变列表U，其约束U必须是 的超类型T。例如

• 我可以将一只猴子添加到猴子列表中，从而产生一个新的猴子列表；
• 我可以将人类添加到猴子列表中，从而生成新的原始人列表（大概是猴子和人类的最小上限）；
• 我可以将一块岩石添加到原始人列表中，从而生成一个新列表Object（假设岩石和原始人没有其他共同祖先）。

这在理论上听起来不错，但根据 JLS，下限U是不合法的。我可以改写：

U以这种方式，编译器将正确推断列表的元素类型与我们要添加的元素类型之间的最小上限。这是合法的。它也很烂。比较：

我是函数式编程的忠实粉丝，但我不希望我的 Java 代码看起来像 Lisp 方言。所以我有三个问题：

1. 怎么回事？为什么<U super T>绑定不合法？这个问题实际上已经在这里被问过（“为什么 Java 类型参数不能有下限？”）但我认为这个问题的措辞有点混乱，那里的答案归结为“它不够有用”，我真的不买。

2. JLS 第 4.5.1 节指出：“与在方法签名中声明的普通类型变量不同，使用通配符时不需要类型推断。因此，允许在通配符上声明下限。” 鉴于static上面的替代方法签名，编译器显然能够推断出它需要的最小上限，所以这个论点似乎被打破了。有人可以说不是吗？

3. 最重要的是：有人能想出一个合法的替代我的方法签名的下限吗？简而言之，目标是让调用代码看起来像 Java ( list.add(monkey)) 而不是 Lisp ( add(list, monkey))。