分割統治の手法は常に問題を同じタイプのサブ問題に分割するのでしょうか? 同じタイプとは、再帰を伴う関数を使用して実装できることを意味します。分割統治は常に再帰によって実装できますか?
ありがとう！
12897 次
8 に答える
21
「常に」は怖い言葉ですが、再帰を使用できない分割統治の状況は考えられません。分割統治法が最初の問題と同じ形式の部分問題を作成するのは、定義によるものです。これらの部分問題は、何らかの基本ケースに到達するまで継続的に分解され、分割数は入力のサイズと相関します。この種の問題では、再帰が自然に選択されます。
詳細については、ウィキペディアの記事を参照してください。
于 2010-02-12T05:06:12.390 に答える
8
分割統治アルゴリズムは、定義上、再帰によって解決できるアルゴリズムです。したがって、答えはイエスです。
于 2010-02-12T05:13:54.123 に答える
1
この質問には、マージソートアルゴリズムを調べるだけで十分です。分割統治 (再帰も含む) を使用したマージ ソート アルゴリズムの実装を理解すると、再帰なしでそれを行うことがいかに難しいかがわかります。
ここで実際に最も重要なことは、big-oh 表記とマージソートの nlogn で表されるアルゴリズムの複雑さです。
マージソートの例として、ボトムアップマージソートと呼ばれる別のバージョンがあります。これは単純で非再帰的なバージョンです。
一般的なシステムでの再帰的なトップダウン マージソートよりも約 10% 遅くなります。詳細については、次のリンクを参照してください。3回目の講義でよく説明されています。
于 2016-11-29T21:09:14.547 に答える
1
はい。分割統治アルゴリズム手法では、与えられた大きな問題を小さなサブ問題に分割します。これらの小さなサブ問題は、サイズが小さいことを除いて、大きな問題に似ている必要があります。
たとえば、サイズ N の配列をソートする問題は、サイズ N/2 の配列をソートする問題と同じです。後者の問題サイズが前者の問題サイズよりも小さいことを除いて。
小さいサブ問題が大きいサブ問題と似ていない場合、分割統治法を使用して大きな問題を解決することはできません。言い換えれば、与えられた問題は、与えられたより大きな問題が、より大きな問題に似た小さなサブ問題に分割できる場合にのみ、分割統治法を使用して解決できます。
于 2014-10-16T18:45:52.547 に答える
0
再帰は、関数自体を定義するプログラミング手法です。この関数は通常、わずかに変更されたパラメーターを使用して自分自身を呼び出します (収束するため)。
- 問題を 2 つ以上の小さな部分問題に分割します。
- 副問題を (再帰的に) 解決することで克服します。
- 副問題の解を元の問題の解に結合します。
于 2015-05-30T21:12:21.120 に答える
0
想像してみてくださいPのサイズの問題でnありS、解決策です。この場合、Pサブ問題に分割するのに十分な大きさの場合、たとえばP1、P2、P3、P4、 ... 、Pk; S1k サブ問題としましょう。また、k サブ問題のそれぞれに対して k 個の解が存在S2しS3ますSk。ここで、サブ問題の各ソリューションを組み合わせると、S 結果を得ることができます。分割統治戦略では、主要な問題が何であれ、すべての下位の問題は同じでなければなりません。たとえば、Pがソートの場合P1、もソートP2でPnある必要があります。したがって、これは本質的に再帰的です。したがって、分割統治は再帰的になります。
于 2019-03-02T20:25:04.073 に答える