问题标签 [lower-bound]

我试图解决的问题如下：

给定一个有向图，找到“覆盖”整个图的最小路径数。多条路径可能经过同一个顶点，但路径的并集应该是所有路径。

对于给定的示例图（见图），结果应该是 2（1->2->4，并且 1->2->3 就足够了）。

通过分割顶点并为连接入顶点和出顶点的每条边分配 1 的下限，并将源链接到每个入顶点，将每个出顶点链接到接收器（它们没有显示在图，因为它会使整个事情变得混乱），现在的问题是在图中找到具有下限约束的最小流量。

但是，我已经读过，为了解决这个问题，我必须找到一个可行的流程，然后按如下方式分配容量：C(e) = F(e) - L(e)。但是，通过给每条Source-vertex edge、vertex-Sink edge、In-Out edge分配一个flow为1，可行的flow是正确的，总的flow等于vertices的个数。但是通过分配新容量，进出边（标记为蓝色）的容量为 0（它们的下限为 1，在我们选择可行流时，它们的流为 1），并且没有流量是可能的。

图 2：我如何选择“可行流程”

但是，从图中您可以清楚地看到，您可以引导一个满足每个“顶点边缘”下限的 2 流。

我是否理解错误的最小流量算法？哪里错了？！

我有一些关于渐近界的例子：上限和下限，我不明白为什么我们要考虑主导项或每个项中的 n 个项。有人可以向我解释一下吗？

渐近上界：

12n^3 + 8n + 20 = O(n^3)

12n^3 + 8n + 20 = O(n^5) [我认为应该是 12n^5]

渐近下界：

12n^3 + 8n + 20 = 欧米茄(n^3)

12n^3 + 8n + 20 = Omega(n)

我阅读了定义，但无法理解为什么它会在下限发生变化以及为什么会像在上限发生变化。

为什么std::lower_bound( )的第一步没有简单的比较？

随着初始步骤std::lower_bound将迭代器it从first列表中更改为中心位置：

之后，算法开始将该中心-it与给定的 进行比较value：

但最简单的情况是在重新定位之前进行一次比较作为初始步骤it：

想象一下，有一个很长的列表，你仍然需要等到std::lower_bound它的当前形式实现，这value < *first是真的。当然它是O(log_2(last - first))，但在这种情况下，它可能是O(1)，只有一行。

我正在使用 lower_bound() 在 weak_ptr 的排序向量中进行搜索

在哪里，类有一个私有sa方法和一个公共方法。调用时会导致段错误。我猜是因为，它返回 empty 。shared_ptr<A>Astring IDgetIDfindAgetIDlock()shared_ptr

我该如何解决？

如何获得下一个最小值到 python 中提供的值？它有任何内置功能吗？

如何找到 3 的下一个最低值或 2 的下一个最大值？预期结果分别为 2 和 3。

给出时间的下限，以生成 k 组中的 n 个数字的单个排序列表。使得最小的 n/k 在前，依此类推。

所以我已经被这个问题困扰了一段时间，我真的不确定如何去做。我知道如何制作决策树，但我不明白在这个问题的背景下我应该如何做。我不一定理解这个问题，但它似乎足够清晰，可以为人们解决。任何正确方向或澄清的观点将不胜感激。

在我之前的问题之后，我还有另一个问题 -

我正在创建一个lower_bound带有二进制搜索之类的版本。随着BinarySearch功能，我找到了插入新项目的位置，并且使用 for 循环，我确实移动了数组的其余部分并插入了正确的项目，以便我可以将其插入到正确的位置。

但是下面的BinarySearch功能不能正常工作。

谁能明白为什么？

如何证明算法的上限和下限？

到目前为止，我认为算法的上限和下限都需要通过考虑所有输入来显示，并表明它不能比 f(n) [上限] 做得更差，也不能比 g(n) 好[下限]。

我的讲师说，对于上限，通常需要证明它[考虑到所有输入]，但对于下限，一个例子就足够了。

这真的让我很困惑。谁能澄清他的意思？

我遇到了一个家庭作业问题：

其中哪一个是最佳算法的最佳情况运行时间的渐近上界，该算法在任意大小的整数数组中找到最大元素n

1. O(log n)
2. O(n ² )
3. 上）
4. O(1)
5. O(n log n)

根据我的理解，它是 O(n)，因为即使它是最好的情况，我们仍然需要扫描 arr 以获得结果。请纠正我

对于算法，边界与最佳/最坏情况有何关系？最坏情况是上限的同义词，最好的情况是下限的同义词吗？或者你至少可以从另一个中推导出一个？或者他们根本没有关系？