[アルゴリズム]分割征服法

分割征服法について

:分割征服法は実は宏大な理論ではなく、これまで学習した合併ソート、高速ソートを実現するために使用された方法論である.アルゴリズム設計では,問題をいくつかの部分に分け,それぞれ部分を征服・分割し,それを征服(解決)して部分を統合し,最終的に問題を解決する方法である.例えば、マージソートは、O(N 2)の時間的複雑さを有する従来の選択ソート、挿入ソート、バブルソートであるため、これらの問題を解決するために、リストを2つの部分に分けて、各リストをソートし、そのソートリストに基づいて最終目標(リストソート)を解く.その結果,分割征服法の大部分(ほぼ100%)は再帰調によって解決された.なぜなら,これまで再帰関数を用いていたときに感じたことであるが,再帰関数自体はfunction(n−1)がすでに除法を持っていることを前提としてfunction(n)の形式(数学的帰納法)を用い,再帰関数のcallstackに蓄積された1つの関数は結局分割征服法の関数を用い続ける.では,再帰呼び出し,分割征服法などをコード上でどのように表現するかを例によって学習する.

上の問題は、連続選択時の最大値がどれくらいであるかの問題です.

まず,

を完全探索法で解き,以下に示す.

max = l[0] for i in range(1, n+1): for j in range(0, n-i+1): std = sum(l[i:i+j]) if std > max : max = std else: continue print(max)

上記の解答は直感的であるが,n 2の時間的複雑さがあるため,より効率的なアルゴリズムを探す必要がある.(条件nが1000000000000の試行がタイムアウトするため)

では分割征服法と再帰関数で解きましょう. def get_biggest(n) : if len(n) == 1: return n[0] else: mid = (0 + len(n)-1)//2 left = get_biggest(n[0:mid+1]) right = get_biggest(n[mid+1:]) l_idx = mid r_idx = mid+1 center_left = n[mid] center_right = n[mid+1] c_l_max = n[mid] c_r_max = n[mid+1] while True: if center_left>c_l_max: c_l_max = center_left if l_idx == 0 : break l_idx -= 1 center_left += n[l_idx] while True: if center_right>c_r_max: c_r_max = center_right if r_idx == len(n)-1 : break r_idx += 1 center_right += n[r_idx] center = c_r_max + c_l_max result = max([left,center,right]) return result print(get_biggest(l))

ドアをいくつか使いました...これは逆に効率を低下させるが,実際にはこの関数の時間的複雑さはO(nlogn)である.ではどんな分割を征服しますか(?)考えてみると、まず、左(インデックス0)から連続値までの最大和(中間インデックスではなく)、右端から中間インデックスまでの最大和を基本的に求めます.そして、真ん中インデックスから真ん中インデックスの両端にかけて最大値を求め、さらに左時の最大値と右時の最大値を加えることで、真ん中から求めた最大値(左、右の2つの部分を併せて考える場合)となる.したがって,最終的に1つのリストを3つの部分(左,右,中)に分け,各連続の最大値を求め,そのうち最大値が最大値となる.しかしこれがどうしてO(nlogn)になるのか???

これは,集計ソートと時間複雑度を求める点火式と同様であり,左,右を求める時間複雑度はそれぞれT(n/2)である.すなわち、n個の要素のリストから2個のn/2個の要素のリストに分けられ、各要素の最大連続値にはT(n/2)が必要である(これは、時間全体の複雑さがT(n))ことを意味する.ここで再帰呼び出しの概念を用いて,T(n/2)は最終的に上記と同様の過程を経て連続数の最大値を求める.すなわち、T(n/2)時間複雑度を有する左側リストの実施においても、これを2つの部分に分けて、今回はT(n/4)+T(n/4)=2 T(n/4)の時間複雑度である.また,最後のタスクの中間から両側連続の最大値の論理を探す必要があるため,O(n)の時間的複雑さが増す.では最終的に.
「T(n)=2*T(n/2)+O(n)」が成り立ち(点化式)、最終的にT(n)が何回二次分割を行う必要があるかという問題は、二次分割の回数によって時間の複雑さを決定し、O(nlogn)で表すことができる.このとき,O(n)

実際,再帰呼び出しで論理を記述することは,前の関数が正常に動作する「仮定」を抱いて関数を記述することであり,論理はかえって簡単である.以前の関数が前提記述関数に正しく戻ると,次の値function(n)を記述することが容易になるからである.

集計ソートの練習

def merge_sort(l): if len(l)==1 or len(l)==0: return l else: mid = (0+len(l)-1)//2 left = merge_sort(l[0:mid+1]) right = merge_sort(l[mid+1:]) idx = 0 result = [] while True: if left[0]>right[0]: result.append(right[0]) right.pop(0) if len(right) == 0: result += left break else: result.append(left[0]) left.pop(0) if len(left) == 0: result += right break return result print(" ".join(list(map(str,merge_sort(l)))))

の最後の部分

:分割征服法はエラトネスのふるいやモジュール演算のように,知識を理解し暗記するよりも技能に近い.接近したときに探索法で全く接近できないなら、他の方法で考えることができるのが「分割征服法」です.問題を複数の部分に分割し、各問題に基づいて問題全体を解決する点==再帰関数の論理」という部分がポイントのようです.