问题标签 [lower-bound]

（感谢 Rich Bradshaw）

我正在为以下难题寻找最佳策略。

作为新的仙王，你有责任绘制王国的奶油沼泽地图。
沼泽笼罩在飘渺的薄雾中，蛋奶沙司散落在各处。
您可以将您的小精灵送过沼泽，并附有在每个点低飞或高飞的指示。
如果小精灵从蛋奶冻上俯冲下来，它会分心，不会完成它的序列。由于雾气很浓，你只知道小精灵是否到达了另一边。

在编码方面..

这将返回小精灵是否退出给定的猛扑序列。

最简单的方法是一次性传递序列。这揭示了“大小”尝试中的所有蛋奶冻岛。
我更喜欢与蛋奶冻的数量成比例的东西 - 但在序列方面存在问题，例如：

也欢迎链接到这个谜题的其他形式。

我正在将一些 C++ 代码转换为 C#，它调用 std::map::lower_bound(k) 在映射中查找其键等于或大于 k 的条目。但是，我看不到任何方法可以用 .NET 的 SortedDictionary 做同样的事情。我怀疑我可以使用 SortedList 实现一种解决方法，但不幸的是，SortedList 太慢（插入和删除键的 O(n)）。我能做些什么？

注意：我找到了一种利用我的特定场景的解决方法......具体来说，我的键是从 0 开始的密集整数，所以我使用 List<TValue> 作为我的字典，列表索引用作密钥，并且搜索等于或大于 k 的密钥只需几个循环迭代即可完成。但是很高兴看到原始问题得到回答。

这可能是一个愚蠢的问题，但有人知道二分搜索是渐近最优的证明吗？也就是说，如果给定一个元素的排序列表，其中对这些对象的唯一允许操作是比较，你如何证明搜索不能在 o(lg n) 中完成？（顺便说一下，这是 lg n 的小 O。）请注意，我将其限制为唯一允许操作是比较的元素，因为有众所周知的算法可以在预期上击败 O(lg n)如果允许您对数据执行更复杂的操作（例如，请参见插值搜索）。

众所周知，堆排序的最坏情况运行时是 Ω(n lg n)，但我无法理解为什么会这样。特别是，堆排序的第一步（创建一个最大堆）需要时间 Θ(n)。然后是 n 次堆删除。我明白为什么每次堆删除都需要时间 O(lg n); 重新平衡堆涉及一个消泡操作，该操作在堆的高度上花费时间 O(h)，并且 h = O(lg n)。但是，我不明白为什么第二步应该采用 Ω(n lg n)。似乎任何单独的堆出队都不一定会导致移动到顶部的节点一直沿树冒泡。

我的问题是 - 有没有人知道堆排序的最佳情况行为的良好下限证明？

有许多算法在 O(n {log n}^k) 时间内运行，其中 k>1。

如果您能为我提供有关以下任何问题的参考，那将非常有帮助：

\Omega{(n {log n}^k)} 下界，其中 k>1。

我知道k=1 有很多例子，例如最接近的对/排序。

我对 C++ 很陌生，不了解 STL 库的所有概念，所以请耐心等待。我编写了以下代码片段（粘贴在下面）来查找排序向量中的 lower_bound。尽管此代码在发布模式下工作正常，但它在调试模式下断言（VStudio-8）。我相信这是因为less_equal<int>不是严格的弱排序。

来自以下线程：stl ordering - strict weak ordering

我确实理解 STL 强加了弱排序，但我仍然不太清楚为什么？

在下面的情况下，我需要使用less_equal<int>，因为我试图在排序向量中找到最接近给定值的元素。

下面的代码片段是否有效？另外，有没有更好的方法呢？此外，任何关于什么是弱和偏序的见解/参考都会有所帮助。

有许多已知是 NP-hard 的优化问题，例如旅行商问题、MAX-SAT 或寻找图的最小色数。鉴于此类问题，我很好奇以下问题的复杂性：

给定一个 NP-hard 优化问题和一个候选解 S，S 是该问题的最优解吗？

直觉上，这似乎很难 co-NP，因为通过猜测更好的解决方案并将其用作见证来反驳优化问题的答案很容易，但我不知道如何证明这一点。事实上，我真的不知道如何推理这个问题的复杂性。

有谁知道这个决策问题的复杂性有什么好的下限？知道这是否是 co-NP 难、PSPACE 难等会非常有趣。

是否有任何具有 STL 函数的库，如std::sort(), std::binary_search(), std::lower_bound()，std::upper_bound()接受 3 路比较谓词（在较少时返回 -1，在相等时返回 0，在大时返回 1）而不是较少谓词（在较少时为真，在相等或大时为假）？

当然，less 谓词可以很容易地从现有的 3 向谓词（如[](A a, B b) { return compare3(a,b)<0; }）中提取出来，但这会导致对谓词的调用次数增加。

multimap提供方法lower_bound和upper_bound。两者都可以将迭代器返回到键大于期望值的值，并lower_bound可能产生完全期望的值。

现在我想要一个迭代器来指向一个键严格小于请求的值。如果它是 amap而不是multimap，这将相对简单地实现，如下所述： 在 C++ Map 中返回严格小于给定键的最大键。但是在 a 中multimap，递减迭代器并不能保证它指向一个严格更小的键。所以我需要反复递减，直到找到一个更小的键。不是特别好。

有没有更优雅的方式来做到这一点？

键通常是浮点数。

基于此处找到的以下定义

返回一个迭代器，该迭代器指向排序范围 [first,last) 中不小于值的第一个元素。第一个版本使用 operator< 或第二个版本使用 comp 进行比较。

什么是 lower_bound() 的 C 等效实现。我知道这将是对二分搜索的修改，但似乎无法准确指出确切的实现。

示例案例：

我尝试的代码如下：