問題 X が問題 Y に還元される場合、逆の還元も可能ですか? 言う
X = 与えられた配列は、すべての要素が異なるかどうかを示します
Y = 比較ソートを使用して配列をソートする
ここで、X は線形時間で Y に減少します。つまり、Y を解くことができれば、X を線形時間で解くことができます。逆は常に真ですか？Xを解けるなら、Yを解けるか? もしそうなら、どのように？
削減とは、次のことを意味します。
Problem X linear reduces to problem Y if X can be solved with:
a) Linear number of standard computational steps.
b) Constant calls to subroutine for Y.
問題 A を定数時間 O(1) で解くことができるが、問題 B には最適な指数時間解 O(2^n) があるとします。問題 A を O(2^n) で解決する (問題 A を B に「還元」する) 非常に複雑な方法も思いつく可能性がありますが、あなたの質問に対する答えが「はい」である場合は、そうする必要があります。非常に難しい問題をすべて O(1) で解けるようにすることができます。確かに、そんなことはあり得ません！
上記の例を考えると：
O(N)ハッシュ テーブルでそれらをバックアップすると、すべての要素が異なるかどうかを判断できます。+ ハッシュ関数のオーバーヘッドの存在を確認できますO(1)(通常は問題になりません)。非比較ベースの並べ替えを行っている場合:
簡単にするために、自然数のリストを並べ替えるとします。並べ替え方法は、スパゲッティの未調理のロッドを使用して説明されています。リスト内の各番号 x について、長さ x のロッドを取得します。(単位を選択する実用的な方法の 1 つは、リスト内の最大数 m をスパゲッティの 1 本の完全な棒に対応させることです。この場合、完全な棒はスパゲッティの m 個の単位に等しくなります。長さ x の棒を得るには、単純に棒を壊します。 1 つの部分が x 単位の長さになるように 2 つに分割し、もう 1 つの部分は破棄します)。
すべてのスパゲッティロッドを手に入れたら、こぶしでゆるく握り、テーブルに下ろして、すべて直立させ、テーブルの表面に置きます. 次に、それぞれのロッドについて、もう一方の手を上からロッドと接するまで下げます。これが明らかに最も長いです。このロッドを取り外して、(最初は空の) 出力リストの先頭に挿入します (または、出力配列の最後の未使用スロットに配置します)。すべてのロッドが取り除かれるまで繰り返します。
したがって、あなたの問題の非常に特殊なケースが与えられた場合、あなたの声明は成り立ちます。ただし、これは一般的なケースには当てはまりません。これは、人々が TSP を解決したと考えるのと非常によく似ていますが、代わりに、特別なアルゴリズムを使用して解決できる一般的な問題の制約付きバージョンを作成しました。
O(N)リダクションの意味を理解していると仮定して、キーと値のペアの配列を使用して解決できる問題があるとしましょう。それは、リストから何かを検索する問題です。O(1)辞書を使用して同じ問題を解決できます。
それは、最初の手法に戻って、それを使用して同じ問題を解決できるということO(1)ですか?
私はそうは思わない。