Divide-and-conquer algorithms

Zwe Naing
Zwe Naing
Jul 24, 2017 · 3 min read

ဒီစာမွာ အဓိကအားျဖင့္ divide-and-conquer algorithms ရဲ႔ သေဘာသဘာဝနဲ႔ သူတို႔ကို ဘယ္လိုခြဲျခမ္းစိတ္ျဖာ(analysis)လုပ္မလဲဆိုတာကို ေရးသြားမွာပါ။ သာမန္အားျဖင့္ ျပႆနာတစ္ခုေျဖရွင္းဖို႔ေပးထားရင္ အလြယ္ကူဆံုးျဖစ္တဲ့ brute force method နဲ႔ ပထမဆံုးေျဖရွင္းေလ့ရွိပါတယ္။ ဆိုလိုတာက ဥပမာ sorting လုပ္တယ္ဆိုပါစို႔။ အလြယ္ကူဆံုးနည္းလမ္းကေတာ့ brute force method ျဖစ္တဲ့ selection sort ပါ။ sorting လုပ္မယ့္ array မွာ minimum သို႔မဟုတ္ maximum ကိုရွာျပီး ငယ္စဥ္ၾကီးလိုက္ သို႔မဟုတ္ ၾကီးစဥ္ငယ္လိုက္လိုအပ္သလိုစီဖို႔ပါ။ ဒါေပမယ့္ သူ႔ရဲ႔ Running time က 𝛩(n²) ပါ။ ေသခ်ာတာကေတာ့ ဒီေနရာမွာ 𝛩(n²) ထက္ပိုေကာင္းေအာင္လုပ္နုိင္ပါတယ္။ Divide-and-conquer paradigm ကိုသံုးတဲ့ merge sort ကို သံုးဖို႔ပါ။ ရလဒ္ကေတာ့ Running time 𝛩(n lg n) ျဖစ္ျပီး နည္းနည္းပိုျပီးျမန္လာမွာပါ။ merge sort ရဲ႔ လိုရင္းကေတာ့ ေပးထားတဲ့ input ကို sorting လုပ္မယ့္အစား တစ္ဝက္စီကို input size 1 ျဖစ္တဲ့အထိဆက္တိုက္ခြဲျပီး တစ္ခုျခင္းစီကို sorting လုပ္ျပီးမွ ျပနေ္ပါင္းဖို႔ပါ။

Three components

Divide-and-conquer algorithms ေတြတိုင္းမွာ တျခား algorithms ေတြနဲ႔မတူတဲ့ မျဖစ္မေနပါတဲ့ သံုးပိုင္းရွိပါတယ္။

Divide — ေပးထားတဲ့ input တစ္ခုကို ေသးငယ္တဲ့အစိတ္အပိုင္းေတြအျဖစ္၊ ေသးငယ္တဲ့ ျပႆနာေလးေတြအျဖစ္ ခြဲတဲ့ အဆင့္ျဖစ္ပါတယ္။ တခ်ိဳ႔ကေတာ့ ႏွစ္ပိုင္းအညီအမ်ွခြဲပါတယ္။ တခ်ိဳ႔က သံုးခု၊ ေလးခုစသည္ျဖင့္ လိုအပ္သလို ခြဲပါတယ္။

Conquer — ရလာတဲ့ ေသးငယ္တဲ့အစိတ္အပိုင္းေလးေတြကို recursively ေျဖရွင္းဖို႔ပါ။ ဥပမာ — merge sort မွာဆိုရင္ အစိတ္အပိုင္းႏွစ္ခုကို recursively sorting လုပ္တဲ့အဆင့္ျဖစ္ပါတယ္။

Combine — ေနာက္ဆံုးရလာတဲ့ ေျဖရွင္းျပီးသား အစိတ္အပိုင္းေတြကို ေပးထားတဲ့ ျပႆနာရဲ႔ အေျဖအျဖစ္ျပန္ေပါင္းဖို႔ပါ။

စိတ္ဝင္စားစရာအေကာင္းဆံုးက တခ်ိဳ႔ျပႆနာေတြမွာ ဒီသံုးခ်က္ကထင္ရွားေပမယ့္ တခ်ိဳ႔ျပႆနာေတြမွာ အစိတ္အပိုင္းေတြရဲ႔အေျဖက မူလျပႆနာနဲ႔ လံုးဝအစပ္အဆက္မရွိပါဘူး။ ဒါေပမယ့္ divde-and-conquer algorithms မွန္ရင္ေတာ့ ဒီသံုးဆင့္အျမဲပါပါတယ္။ တစ္ခုနဲ႔ တစ္ခုကြာတာက တခ်ိဳ႔ျပႆနာေတြမွာ Divide အဆင့္မွာ အခ်ိန္အမ်ားၾကီးေပးရျပီး တခ်ိဳ႔ျပႆနာေတြကေတာ့ Combine အဆင့္မွာ Process လုပ္ရတာၾကာပါတယ္။ Conquer အဆင့္ကေတာ့ ရလာတဲ့အစိတ္အပိုင္းေတြကို မေပါင္းမွီ recursively ေျဖရွင္းရတဲ့အပိုင္းျဖစ္ပါတယ္။

ဥပမာေပးရရင္ Merge sort မွာဆိုရင္ ေပးထားတဲ့ input size = n ကို ထက္ဝက္စီ (input size = n/2) တစ္ဆင့့္ျပီးတစ္ဆင့္ ေနာက္ဆံုး input size = 1 တစ္ခုထဲ က်န္တဲ့အထိခြဲပါတယ္။ ဒီအဆင့္က Divide ပါ။ ျပီးမွ ႏွစ္ခုႏွစ္ခုဆီျပန္ေပါင္းျပီး ေနာက္ဆံုး sorting လုပ္ျပီးသား input ကိုျပန္ရပါတယ္။ ဒီအဆင့္က Combine အဆင့္ပါ။ Conquer အဆင့္ကေတာ့ Combine မလုပ္ခင္ ေပါင္းမယ့္ အစိတ္အပိုင္းႏွစ္ခုကို sorted order ျဖစ္ေအာင္စီတဲ့ အဆင့္ျဖစ္ပါတယ္။

မ်ားေသာအားျဖင့္ divide-and-conquer algorithms ေတြက သာမန္ brute force methods ေတြထက္ပိုျမန္ပါတယ္။ ျပီးေတာ့ ျဖတ္ထိုးဥာဏ္လည္း ပိုလိုပါတယ္။

Recurrence Equation

ေနာက္ထပ္စဥ္းစားဖို႔လိုတာက ဒီ Divide-and-conquer algorithms ေတြကို mathematically ဘယ္လိုေဖာ္ျပမလဲဆိုတာပါ။ သာမန္ Looping ကို သံုးတဲ့ algorithms ေတြလို တိုက္ရိုက္ေဖာ္ျပလို႔မလြယ္ပါဘူး။ ဒါေၾကာင့္ အစိတ္အပိုင္းေတြကို Process လုပ္ဖို႔လိုတဲ့ အခ်ိန္နဲ႔ပဲေဖာ္ျပေလ့ရွိပါတယ္။ T(n) = Divide(n) + Conquer(n) + Combine(n) ။ recurrence equation လို႔ေခၚပါတယ္။ အေပၚမွာေျပာခဲ့တဲ့အတိုင္း အပိုင္းသံုးပိုင္းပါဝင္ပါတယ္။ တစ္နည္းအားျဖင့္ T(n) = a T(n/b) + f(n) လို႔လဲေဖာ္ျပနုိုင္ပါတယ္။ a ကေတာ့ တစ္ဆင့္ခ်င္းစီမွာ ခြဲမယ့္ subprobems ပမာဏျဖစ္ပါတယ္။ b ကေတာ့ subproblem တစ္ခုခ်င္းစီက မူလ problem ရဲ႔ ဘယ္ေလာက္ရွိသလဲဆိုတာပါ။ f(n) ကေတာ့ Divide and combine အဆင့္နွစ္ခုရဲ႔ ၾကာခ်ိန္ျဖစ္ပါတယ္။

ဥပမာ — merge sort အတြက္ recurrence equation က T(n) = 2 T(n/2) + 𝛩(n) ပါ။ Strassen ရဲ႔ နံမည္ၾကီး matrix multiplication ဆိုရင္ T(n) = 7 T(n/2) + 𝛩(n²) ပါ။ ပထမတစ္ခုမွာ မူလ input ရဲ႔ တစ္ဝက္စီျဖစ္တဲ့ အစိတ္အပိုင္းႏွစ္ခုအျဖစ္ခြဲပါတယ္။ Combine အဆင့္ကေတာ့ 𝛩(n) ပါ။ ဒုတိယတစ္ခုမွာေတာ့ တစ္ဝက္စီအစိတ္အပိုင္းခုႏွစ္ခုခြဲပါတယ္။ Combine အဆင့္ကေတာ့ 𝛩(n²) ပါ။ ဒီ equations နွစ္ခုစလံုးမွာ constant time 𝛩(1) ျဖစ္တဲ့ Divide အပိုင္းကို ထည့္ျပီးေဖာ္ျပမထားပါဘူး။

Solving recurrences

အခုဆုိရင္ divide-and-conquer algorithms ေတြကို equations ေတြသံုးျပီး လိုရင္းတိုရွင္းေျပာလို႔ရပါျပီ။ ဒါေပမယ့္ ဒီ Recurrence Equation ရဲ႔အားနည္းခ်က္က Algorithm က အဆိုးဆံုးအေျခအေန (worst case scenario) မွာ ဘယ္ေလာက္အခ်ိန္ယူမလဲ (upper-bound) နဲ႔ အေကာင္းဆံုးအေျခအေန (best case scenario) မွာေကာ ဘယ္ေလာက္ျမန္သလဲ (lower bound) ကို ျပနိုင္စြမ္းမရွိပါဘူး။ ဒါေပမယ့္ ဒီ equation မွာပါတဲ့ အခ်က္အလက္ကေနတစ္ဆင့္တြက္ယူလို႔ရပါတယ္။ အထိေရာက္ဆံုးနည္းလမ္းကေတာ့ Recurrence Tree ပါ။

ေအာက္ကပံုမွာျပထားတာကေတာ့ Merge sort အတြက္ recurrence tree ပါ။ ပံုမွာ ျမင္ရတဲ့အတိုင္း ညာဘက္ကေတာ့ အဆင့္တစ္ဆင့္ခ်င္းစီမွာ process လုပ္ရမယ့္ ပမာဏ cn ျဖစ္ပါတယ္။ ဘယ္ဘက္မွာေတာ့ level 0,1,2, …,lg n အထိပါ။ ေနာက္ဆံုးအဆင့္မွာ input size = 1 ျဖစ္တဲ့အတြက္ process လုပ္ခ်ိန္က constant time O(1) ပါ။ အားလံုးကိုေပါင္းလိုက္ရင္ Arithmetic series တစ္ခုရပါတယ္။ ဒီေနရာမွာ Arithmetic series formula ကိုသံုးလိုက္ရင္ ေနာက္ဆံုး Running time 𝛩(n lg n) ကိုရပါတယ္။ ဒီနည္းလမ္းကေတာ့ recurrences ေတြကို ေျဖရွင္းနည္းေတြထဲကတစ္ခုျဖစ္ပါတယ္။ အဓိကကေတာ့ Divide-and-conquer algorithm တစ္ခု အစိတ္အပိုင္းဘယ္ႏွစ္ခုခြဲသလဲ၊ တစ္ဆင့္ခ်င္းစီမွာ process ဘယ္ေလာက္လုပ္ရသလဲနဲ႔ level အဆင့္ဘယ္ႏွစ္ခုလုပ္ရသလဲ စတာေတြကို ခ်ေရးျပီး Pattern တစ္ခုရေအာင္ရွာဖို႔ပါ။ ျပီးေတာ့ အားလံုးကို ေပါင္းလိုက္ျပီးရင္ မ်ားေသာအားျဖင့္ေတာ့ Arithmetic သို႔မဟုတ္ Geometric series တစ္ခုရလာပါတယ္။ လိုအပ္တဲ့ formula အသံုးျပဳလိုက္ရင္ asymptotic-bound ကို အလြယ္တကူရွာလို႔ရပါတယ္။

Recursion tree of merge sort

တျခား Substitution method, iteration method နဲ႔ master method ေတြကို အသံုးျပဳနိုင္ပါတယ္။ Iteration method ကေတာ့ recurrence tree ကဲ့သို႔ asymptotic-bound ကို ခန္႔မွန္းဖို႔ပါ။ တစ္ခုရွိတာက iteration method နဲ႔ recurrence tree ဆြဲစဥ္မွာ အမွားမ်ားပါတယ္။ Substitution method ကေတာ့ ရလာတဲ့ ခန္႔မွန္း asymptotic ကို သက္ေသျပဖို႔ပါ။ Mathematical induction နဲ႔ ဆင္တူပါတယ္။ Master method ကေတာ့ algorithm ရဲ႔ recurrence equation က T(n) = a T(n/b) + O(n^d) ကဲ့သို႔ ပံုစံရွိရင္ formula ထဲမွာ ထည့္လိုက္ျပီး asymptotic bound ကို အလြယ္တကူရွာနိုင္ပါတယ္။ Master theorem မွာ Case သံုးခုရွိပါတယ္။ ေအာက္က ပံုမွာၾကည့္နိုင္ပါတယ္။

Master Method

Divide-and-conquer algorithms ေတြက programming မွာ ခဏခဏေတြ႔ရတဲ့ algorithms ေတြျဖစ္သလို စိတ္ဝင္စားစရာလည္းေကာင္းပါတယ္။ နားလည္ထားရင္ အတိုင္းအတာတစ္ခုထိ အက်ိဳးရွိမယ္လို႔ယံုၾကည္ပါတယ္။ ေနာက္ထပ္ Randomized algorithms ေတြနဲ႔ advanced data structures ေတြအေၾကာင္းကို ေနာက္ထပ္ေရးသြားပါမယ္။

Share scientific knowledge!

Connect with me on Linkedin @ https://www.linkedin.com/in/zwenaing/

References —

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2014). Introduction to algorithms. Cambridge, MA: The MIT Press.

Muhammad, P. R. (n.d.). Retrieved July 23, 2017, from http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/mergeSort.htm

Algorithm — Master method to find time complexity for recursive calls. (2014, January 24). Retrieved July 23, 2017, from https://acrocontext.wordpress.com/2014/01/25/algorithm-master-method-to-find-time-complexity-for-recursive-calls/

Zwe Naing

Written by

Zwe Naing

Software Engineer

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade