二进制ish通过部分有序集进行搜索

Question

我有一个有趣的功能。它将{1，...，n}的子集到正整数，即 $ f：p（[n]）\ lightarrow z ^ + $ 。 我知道如果s是s'的子集， $ f（s）。此外，如果s和s'具有相同的基数，则f由f的排序是词典，例如 $ f（\ {1,2,4 \}）。 给出一个值 z ，我想找到这样的 $ f（s）<= z $ 和 $ f（s）<= f（t）<= z $ 暗示 $ f（s）= f（t）$ - 也就是说，我想在[n]的子集的栅格上进行搜索。

如果我知道订购是完美的词典，我会使用简单的二进制搜索。我不知道，我相信它不是（例如， $ f（\ {1,2,3,4,5,6 \}）$ 可能大于 $ f（\ {7 \}）$ ）。是否有一个很好的O（n）算法在POSET上进行此搜索？显然，对于任何可观的大小，我必须在飞行中计算f，不能依赖内存存储。

在评论中讨论后澄清： 特定 $ f $ 我处理是附加 - 具体来说， $ f（s）=sum_ {k \在s} g（k）+ f（\ imptyset）$ 中，使用 $ g $ 一个单调增加的函数。这可能比一般情况更容易（这也很有意思，而不是我的特定问题）。

Answer 1

这里是一种简单的算法，它在 $ o（n ^ 2）$ 时间和 $ o（n） $ 空格，假设 $ f（\ imptyset）$ ， $ f（\ {1 \}） $ ， $ f（\ {2 \}）$ ， $ \ cdots $ ， $ f（\ {n \}）$ 在数组中给出。

起始想法与他评论中的OP给出的内容相同。 “我们将使用Lexicography顺序搜索大小k的子集，每个 $ k $ from $ 0 $ to $ n $ 。保留具有 $ f $ 。“

的最佳值

问题是如何搜索 $ f $ 的最佳值 $ k $ ，命名为 $ b_k $ ，在 $ o（n）$ 时间。而不是二进制搜索，我们将检查 $ n $ ， $ n-1 $ ，\ cdots， $ 1 $ 应在最佳子集中逐个包含，通过在子集上的基本命令的实际优势。

1. initialize $ b_k= f（\ imptyset）$ 。 $ \ b_k $ 将是大小的子集中的最佳值 $ k $ 在此过程结束时。
2. initialize $ count= 0。$ $ \ count $ 是我们拥有的元素数到目前为止，在最好的子集中。
3. 检查 $ f（\ {n \}）$ 。如果 $ b_k + f（\ {n \}）+ f（\ {1,2，\ cdots，k-count -1 \}）\ le z $ ，必须包含$ n $ 。添加 $ f（\ {n \}）$ 到 $ b_k $ 并添加1到 $ Count $ 。
4. 检查 $ f（\ {n-1 \}）$ 。如果 $ b_k + f（\ {n-1 \}）+ f（\ {1,2，\ cdots，k-count-1 \}）\ le z $ ， $ n-1 $ 必须包括。添加 $ f（\ {n-1 \}）$ 到 $ b_k $ 并添加1到< SPAN Class=“math-container”> $ count $ 。
5. 等等。
6. 直到我们已经检查了 $ f（\ {1 \}）$ 或 $ count== k $ < / span>。

我们可能会奇怪，如果它需要 $ o（n）$ 计算每个 $ f（\ {1 ，2，\ cdots，k-count-1 \}）$ ，计算每个 $ b_k $ 单独使用 $ O（n * n）$ 时间。但是，由于<跨度类=“math-container”> $ f $ 是附加的，我们可以计算 $ f（\ {1 \}）$的所有前缀和， $ f（\ {2 \}）$ ， $ \ cdots $ ，< SPAN Class=“Math-Container”> $ F（\ {n \}）$ $ o（n）$ 时间。然后它需要 $ o（1）$ 以访问每个前缀。

因为搜索 $ b_k $ take $ o（n）$ 时间，对于每个 $ k $ 从 $ 0 $ 到 $ n $ ，总运行时间是 $ o（n ^ 2）$ 。

---

上面的算法的描述跳过 $ f（\ imptyset）\ gt z $ 时最简单的情况。在这种情况下，算法应该返回没有这样的子集。