تقسیم و حل:

حل مسائل با استفاده از تقسیم و حل

مسائل سنگین به مسائل کوچکتری تقسیم می‌شوند، هرکدام از این مسائل کوچک را زیر مسئله می‌گویند. در نهایت حل مسائل کوچک سریع‌تر و راحت از مسائل بزرگ می‌باشد.

سپس با ترکیب حل مسائل کوچک جواب مسئله بزرگ به دست می‌آید.

حل مسئله جستجوی دودویی به روش تقسیم و حل:

این الگوریتم برای لیست مرتب ارائه شده است. همانطور که می‌دانید در لیست مرتب و نامرتب بدترین حالت جستجوی یک عدد روش خطی یا $O(n^2)$ می‌باشد. اما در مورد لیست مرتب با جستجوی دودویی مرتبه زمانی $O(\log {n})$ خواهد بود.

عملکرد روش جستجوی دودویی:

در هر مرحله عنصر میانه را مشخص می‌کنیم اگر $x$ برابر عنصر میانی باشد یعنی محل $x$ پیدا شده است در غیر اینصورت اگر $x$ بزرگتر از عنصر میانه باشد جستجو را به همین روش در نیمه راست انجام داده و اگر $x$ کوچکتر از عنصر میانه باشد جستجو را در نیمه چپ انجام می‌دهیم.

این کار را آنقدر تکرار می‌کنیم تا یا $x$ پیدا شود و یا با اندیس $h$ برابر شود یا از آن عبور کند.

مثال:

x = 37

 7 , 9 , 11 , 13 , 18 , 24 , 31 , 37
--- --- ---- ---- ---- ---- ---- ----
 0   1   2    3    4    5    6    7

l = 0 ; h = 7

mid = [(l + h)/2] = [(0+7)/2] = 3

 7 , 9 , 11 , 13 , 18 , 24 , 31 , 37
             xxxx ---- ---- ---- ----
 0   1   2    3    4    5    6    7

l = 3 ; h = 7

mid = [(3+7)/2] = 5

 7 , 9 , 11 , 13 , 18 , 24 , 31 , 37
                       xxxx ---- ----
 0   1   2    3    4    5    6    7

l = 6 ; h = 7

mid = [(6+7)/2] = 6

 7 , 9 , 11 , 13 , 18 , 24 , 31 , 37
                            xxxx ----
 0   1   2    3    4    5    6    7

l = 7 ; h = 7

mid = [(7+7)/2] = 7

 7 , 9 , 11 , 13 , 18 , 24 , 31 , 37
                                 ^^^^
 0   1   2    3    4    5    6    7

مثال:

x=6

m=5 \Rightarrow m=2 \Rightarrow m=3

جواب مسئله بالا با استفاده از روش درختی و محاسبه میانگین جستجوی موفق و ناموفق در یک لیست:

میانگین جستجوی موفق:

\frac{1+(2*2)+(4*3)+(4*4)}{11}=\frac{33}{11}=3

میانگین جستجوی ناموفق:

\frac{(4*3)+(8*4)}{12}=\frac{44}{12}=3.66

حل مسئله مرتب‌سازی ادغام یا Merge Sort به روش تقسیم و حل:

برای مرتب‌سازی اعداد به صورت صعودی یا نزولی از این روش استفاده می‌شود، در هر مرحله لیست به دو لیست کوچکتر تقسیم می‌شود‌، عمل تقسیم لیست تا زمانی انجام می‌شود که در آخرین تقسیم طول هر لیست برابر یک عنصر شود. آنگاه عمل ادغام و مرتب‌سازی آغاز می‌شود.

هر بار در زیرشاخه‌ها دو لیست با یکدیگر مقایسه و مرتب و ادغام می‌شوند تا زمانی که تمام لیست مرتب شود.

نکته: مرتبه زمانی الگوریتم مرتب‌سازی ادغام در بهترین حالت و حالت متوسط و بدترین حالت $O(n\log_{2} n)$ می‌باشد.

حل مسئله مرتب سازی سریع به روش تقسیم و حل:

در این مرتب‌سازی اولین عنصر همیشه به عنوان عنصر محوری و یک عنصر فرضی به نام Max بعد از آخرین عنصر در نظر گرفته می‌شود. در هر مرحله شمارنده $i$ از سمت چپ بعد از عنصر محوری آغاز می‌شود و شمارنده $j$ از سمت راست از عنصر Max آغاز شده و در هر مرحله یکی از آن کم می‌گردد. از سمت چپ به راست باید عنصر محوری از محتوای $i$ بزرگتر باشد تا $i$ اضافه گردد همچنین عنصر محوری باید از محتوای $j$ کوچکتر باشد تا از $j$ یکی کم شود اگر الگوریتم متوقف شود یکی از شرط های زیر برقرار است:

شرط اول) اگر $i < j$ شود محتوای $j$ و $i$ عوض می‌شود.

شرط دوم) اگر $i$ از $j$ عبور کند محتوای $j$ با عنصر محوری عوض می‌شود.

نکته: مرتبه زمانی الگوریتم مرتب‌سازی سریع در بهترین حالت و حالت متوسط $O(n\log_{2} n)$ در بدترین حالت $O(n^2)$ می‌باشد. بدترین حالت زمانی است که آرایه از قبل مرتب باشد.

حل مسئله پیدا کردن max و min یک لیست به روش تقسیم و حل:

هربار لیست به دو قسمت تقسیم می‌شود تا زمانی که حداقل و حداکثر طول لیست‌های تقسیم شده برابر "یک" یا "دو" شوند. آنگاه اگر لیست تک عنصری باشد max و min برابر این یک عنصر خواهد بود و اگر لیست دو عنصری باشد بین دو عنصر max و min به راحتی قابل تشخیص خواهد بود. مرتبه زمانی این الگوریتم $O(n)$ است.

مثال: در لیست زیر بزرگترین و کوچکترین عنصر را مشخص کنید

حل مسئله فیبوناچی با روش تقسیم و حل:

در این الگوریتم دنباله‌ای از اعداد تولید می‌شود که هر عدد با جمع دو عدد قبلی به دست می‌آید برای مثال برای محاسبه‌ی جمله‌ی بیستم دنباله‌ی فیبوناچی باید مقادیر 19 جمله قبلی محاسبه شود. مرتبه زمانی این الگوریتم $O(n^2)$ و از نوع نمایی می‌باشد.

int fibo(int n){
    if(n <= 1)
        return n;
    return fibo(n - 1) + fibo(n - 2);
}

1, 1, 2, 3, 5, 8, 13, 21, \ldots

ضرب ماتریس‌ها با استفاده از روش استراسن با تقسیم و حل:

عملیات ضرب ماتریس دارای مرتبه زمانی $O(n^3)$ می‌باشد. اما در روش استراسن تعداد ضرب‌ها کاهش یافته و منجر به کاهش زمان اجرا و مرتبه‌ی زمانی می‌شود.

برای ضرب ماتریس‌ها به روش استراسن در هر مرحله ماتریس‌ها کوچک‌تر می‌شوند تا عمل ضرب بهتر انجام شود. تابع بازگشتی استراسن در هر مرحله 7 بار فراخوانی می‌شود.

نکته: منظور از مسئله کوچک این است که در آن مرحله ضرب به روش معمولی انجام می‌شود.

نکته: برای ضرب ماتریس‌های کوچک استفاده از روش استراسن مقرون به صرفه نیست.

نکته: در ضرب معمولی دو ماتریسی تعداد عمل ضرب برابر است با ³(مرتبه ماتریس)

نکته: تعداد ضرب‌های روش استراسن $T(n) = 7T(\frac{n}{2})$ و در روش معمولی (برای مسئله ی کوچک): $T(n) = n^3$ برای مثال $T(2) = 8$

تقسیم و حل