問題タブ [lower-bound]

(Rich Bradshaw に感謝)

次のパズルの最適な戦略を探しています。

新しい妖精の王として、王国のカスタード湿地の地図を作成するのはあなたの義務です。
湿地は空気のような霧に覆われ、カスタードの島々が散らばっています。
各ポイントで低くまたは高く飛ぶように指示して、ピクシーを沼地に送ることができます。
ピクシーがカスタードの上に急降下すると、気が散ってシーケンスを完了できません。霧が濃いので、ピクシーが向こう側に来たかどうかしかわかりません。

コーディング用語で..

これは、指定された一連の急降下で妖精が退出したかどうかを返します。

最も簡単な方法は、1 回の急降下だけでシーケンスを渡すことです。これにより、「サイズ」試行ですべてのカスタード島が明らかになります。
カスタードの数に比例したものがいいのですが、次のようなシーケンスに問題があります。

このパズルの他の形式へのリンクも歓迎します。

一部のC++コードをC＃に変換していますが、std :: map :: lower_bound（k）を呼び出して、キーがk以上のエントリをマップ内で検索します。ただし、.NETのSortedDictionaryで同じことを行う方法はありません。SortedListを使用して回避策を実装できると思いますが、残念ながら、SortedListは遅すぎます（キーの挿入と削除にはO（n））。私に何ができる？

注：特定のシナリオを利用する回避策を見つけました...具体的には、キーは0を少し超える整数の密集した集団であるため、辞書としてList <TValue>を使用し、リストインデックスは次のように機能します。キー、およびk以上のキーの検索は、数回のループ反復でのみ実行できます。しかし、元の質問が答えられるのを見るのはそれでもいいでしょう。

This may be a silly question, but does anyone know of a proof that binary search is asymptotically optimal? That is, if we are given a sorted list of elements where the only permitted operation on those objects is a comparison, how do you prove that the search can't be done in o(lg n)? (That's little-o of lg n, by the way.) Note that I'm restricting this to elements where the only operation permitted operation is a comparison, since there are well-known algorithms that can beat O(lg n) on expectation if you're allowed to do more complex operations on the data (see, for example, interpolation search).

ヒープソートの最悪の場合の実行時間はΩ（nlg n）であることはよく知られていますが、これがなぜであるかを理解するのに苦労しています。特に、ヒープソートの最初のステップ（最大ヒープの作成）には時間Θ（n）がかかります。その後、n個のヒープが削除されます。各ヒープの削除に時間がかかる理由を理解していますO（lg n）; ヒープのリバランスには、ヒープの高さで時間O（h）を要するバブルダウン操作が含まれ、h = O（lg n）です。しかし、私にはわからないのは、この2番目のステップでΩ（n lg n）が必要な理由です。個々のヒープのデキューによって、必ずしもノードがツリーの一番下に移動したとは限らないようです。

私の質問は-ヒープソートの最良の振る舞いの良い下限の証拠を知っている人はいますか？

O(n {log n}^k)-time (k>1) で実行される多くのアルゴリズムがあります。

次のような問題について参考にしていただけると助かります。

\Omega{(n {log n}^k)} 下限、ここで k>1。

k=1 には多くの例があることを知っています。たとえば、最も近いペア/並べ替えです。

私は C++ の初心者で、STL ライブラリのすべての概念を理解していないので、ご容赦ください。ソートされたベクターで lower_bound を見つけるために、次のコード スニペット (下に貼り付け) を作成しました。このコードはリリース モードでは問題なく動作しますが、デバッグ モード (VStudio-8) ではアサートします。これはless_equal<int>厳密に弱い順序付けではないためだと思います。

次のスレッドから: stl の順序付け - 厳密な弱い順序付け

STLによって弱い順序付けが課されていることはある程度理解していますが、その理由はまだよくわかりません。

以下の私の場合less_equal<int>、ソートされたベクトルで特定の値に最も近い要素を見つけようとしているので、使用する必要があります。

以下のコード スニペットは有効ですか? また、それを行うより良い方法はありますか？また、正確に何が弱く、部分的な順序であるかについての洞察/参照も役立ちます。

巡回セールスマン問題、MAX-SAT、グラフの最小色数の検出など、NP困難であることが知られている多くの最適化問題があります。この種の問題を考えると、私は次の問題の複雑さに興味があります。

NP困難最適化問題と候補解Sが与えられた場合、Sは問題の最適解ですか？

直感的には、より良い解決策を推測してそれを証人として使用することで最適化問題への答えに反論するのは簡単なので、これは共同NP困難であるように思われますが、これをどのように示すかわかりません。実際、私はこの問題の複雑さについて推論する方法を本当に知りません。

この決定問題の複雑さに関する適切な下限を知っている人はいますか？これがco-NPハード、PSPACEハードなどであるかどうかを知ることは本当に興味深いでしょう。

std::sort()、、、std::binary_search()のようstd::lower_bound()なSTL 関数を備えたライブラリはありますstd::upper_bound()か?

もちろん、少ない述語は既存の 3 方向の述語 ( など[](A a, B b) { return compare3(a,b)<0; }) から簡単に作成できますが、これにより、述語への呼び出しが余分に発生します。

multimapメソッドlower_boundと を提供しますupper_bound。どちらも、必要な値よりも大きなキーを持つ値にイテレータを返すlower_bound可能性があり、正確に必要な値が得られる可能性があります。

ここで、キーが要求された値よりも厳密に小さい値へのイテレータが必要です。それがmapではなく である場合multimap、ここで説明されているように、これを達成するのは比較的簡単です: Returning the maximum keystrictly less than the given key in a C++ Map . しかし、multimapでは、反復子をデクリメントしても、厳密に小さいキーを指すようになるとは限りません。したがって、より小さなキーが見つかるまで、繰り返しデクリメントする必要があります。特にいいじゃない。

これを行うよりエレガントな方法はありますか？

通常、キーは浮動小数点になります。

ここにある次の定義に基づいています

値未満を比較しない、ソートされた範囲[first、last）の最初の要素を指すイテレーターを返します。比較は、最初のバージョンの場合はoperator <、2番目のバージョンの場合はcompのいずれかを使用して行われます。

lower_bound（）のCと同等の実装は何でしょうか。二分探索の修正になることは理解していますが、正確な実装を正確に特定することはできないようです。

サンプルケース：

私が試したコードを以下に示します。