قضیه اصلی واکاوی الگوریتم‌ها

از ویکی‌پدیا، دانشنامهٔ آزاد
نسخه دست نویس استین
نسخه دست نویس استین

قضیه اصلی واکاوی (تحلیل) الگوریتم‌ها که حالتی خاص از روش اکرا-بازی در تحلیل الگوریتم‌ها است ، یک راه حل سرراست برای حالت‌های مجانبی که در عمل برای حل انواع روابط بازگشتی رخ می‌دهند، ارائه می‌کند. این قضیه با کتاب درسی معروف مقدمه‌ای بر الگوریتم‌ها نوشتهٔ کرمن، لیسرسن، ریوست و استین به شهرت رسید. این قضیه در بخش ۴٫۳ دراین کتاب معرفی شده‌است و متعاقباً در بخش ۴٫۴ به اثبات رسیده‌است. هرچند که نمی‌توان تمامی روابط بازگشتی را به کمک قضیهٔ اصلی حل کرد.

شکل کلی[ویرایش]

قضیهٔ اصلی روابطی را مورد بررسی قرار می‌دهد که به شکل زیر باشند:

معنای علائم به کار رفته در استفاده از رابطهٔ فوق برای یک الگوریتم بازگشتی، به شرح زیر است: *n اندازهٔ مسئله‌است.

a تعداد زیرمسئله هاست.

  • n/b اندازهٔ هر یک از زیرمسئله هاست. (در اینجا فرض شده‌است که اندازهٔ همهٔ زیرمسئله‌ها با هم برابر است.)
  • (f(n هزینهٔ بخش غیر بازگشتی است که شامل هزینهٔ تقسیم مسئله به زیرمسئله‌ها و هزینهٔ ادغام پاسخ به زیرمسئله هاست.

الگوریتم فوق به صورت بازگشتی مساله را به تعدادی از زیرشاخه ها تقسیم می کند که هر یک از مسایل فرعی با اندازه ( n / b ) است . درخت حل آن گره ای برای هر تماس بازگشتی دارد که فرزندان آن گره سایر تماس های حاصل از آن تماس هستند. برگهای درخت موارد اصلی بازگشت هستند ، مقادیر کوچک (از اندازه کمتر از k) که برگشت نمی کنند.

قضیه اصلی واکاوی غالباً مرزهایی را به صورت نامتعارفی به برخی از الگوریتم های تقسیم و به صورت بازگشتی می دهد که یک پارتیشن ورودی را به مقادیر کوچکتر با اندازه های مساوی تقسیم می کند ، مقادیر کوچک فرعی را به صورت بازگشتی حل می کند ، و سپس راه حل های فرعی را با هم ترکیب می کند تا راه حلی برای مسئله اصلی ارائه دهد. زمان چنین الگوریتمی را می توان با اضافه کردن کارهایی که در سطح بالای بازگشت آنها (برای تقسیم مشکلات در زیرمجموعه ها و سپس ترکیب راه حل های فرعی) بیان شده و همزمان با زمان انجام شده در تماس های بازگشتی الگوریتم,انجام می دهند.

طبق قضیه اصلی سه حالت داریم :

1. f(n) = Θ(nc) در حالی که c < Logba نتیجه می شود T(n) = Θ(nLogba)

2. If f(n) = Θ(nc) در حالی که c = Logba نتیجه می شود T(n) = Θ(ncLog n)

3.If f(n) = Θ(nc) در حالی کهc > Logba نتیجه می شود T(n) = Θ(f(n))

در سه حالت می‌توان یک حد مجانبی مشخص کرد:

حالت ۱[ویرایش]

شکل کلی[ویرایش]

اگر شرط وجود داشته باشد به طوری که رابطهٔ برقرار باشد،

درخت حل
درخت راه حل

آن گاه داریم:

مثال اول[ویرایش]

همان طور که در فرمول فوق دیده می‌شود، متغیرها دارای مقادیر زیر هستند:

، ، ،

حال باید برقراری معادلهٔ زیر را بررسی کنیم:

اگر مقادیر متغیرها را در این رابطه جایگزین کنیم، خواهیم داشت:

درخت بازگشتی
درخت بازگشت

با انتخاب داریم:

از آن جایی که معادلهٔ بالا برقرار است، حالت اول قضیهٔ اصلی را برای رابطهٔ بازگشتی به کار می‌بریم و از نتیجهٔ زیر استفاده می‌کنیم:

اگر مقادیر فوق را در رابطهٔ بالا قرار دهیم، در نهایت خواهیم داشت:

از این رو رابطهٔ بازگشتی داده شده (T(n از(Θ(n³ است.

(راه حل دقیق رابطهٔ بازگشتی نیز این نتیجه را تأیید می‌کند، که در آن ، بافرض است.)

  • حالت ۲

شکل کلی[ویرایش]

اگر داشته باشیم:

آن گاه خواهیم داشت:

مثال[ویرایش]

همان طور که در فرمول فوق مشاهده می‌شود، متغیرها مقادیر زیر را اختیار می‌کنند:

، ، ، ،

حال می‌بایست برقراری رابطهٔ زیر را بررسی کنیم (در حالتی که k=۰ باشد):

درخت راه حل
درخت راه حل

اگر مفادیر متغیرها را،از رابطهٔ بالا در این رابطه جایگزین کنیم، خواهیم داشت:

از آن جایی که این رابطه برقرار است، حالت دوم قضیهٔ اصلی را برای رابطهٔ بازگشنی به کار می‌بریم و از نتیجهٔ زیر استفاده می‌کنیم:

با جایگزین کردن مقادیر فوق در این رابطه در نهایت خواهیم داشت:

از این رو رابطهٔ بازگشتی داده شدهٔ (T(n از (Θ(n log n است.

(راه حل دقیق رابطهٔ بازگشتی نیز این نتیجه را تأیید می‌کند، که در آن ، بافرض است.)

حالت ۳[ویرایش]

شکل کلی[ویرایش]

اگر شرط وجود داشته باشد به طوری که رابطهٔ برقرار باشد و همچنین اگر برای nهای به اندازهٔ کافی بزرگ ثابت وجود داشته باشد به گونه‌ای که رابطه زیر برقرار باشد:

آنگاه خواهیم داشت:

مثال[ویرایش]

همان طور که در فرمول فوق دیده می‌شود، متغیرها مقادیر زیر را اختیار می‌کنند:

، ، ،

حال می‌بایست برقراری معادلهٔ زیر را مورد بررسی قرار دهیم:

اگر مقادیر متغیرها را طبق روابط بالا قرار دهیم و مقدار را انتخاب کنیم، خواهیم داشت:

از آن جایی که معادلهٔ فوق برقرار است، حال باید شرط دوم را مورد بررسی قرار دهیم. به عبارت دیگر باید درستی رابطهٔ زیر را مورد بررسی قرار دهیم:

اگر بار دیگر مقادیر متغیرها را طبق روابط بالا قرار دهیم، خواهیم داشت:

اگر را برگزینیم، آن گاه:

پس خواهیم داشت:

اگر بار دیگر مقادیر لازم را قرار دهیم، رابطهٔ زیر به دست می‌آید:

از این رو رابطهٔ بازگشتی داده شده (T(n از (Θ(n² است.

(راه حل دقیق رابطهٔ بازگشتی نیز این نتیجه را تأیید می‌کند، که در آن ، بافرض است.)


در روش درخت بازگشتی ، کل کارهای انجام شده را محاسبه می کنیم. اگر کارهایی که در برگها انجام می شود چند جمله ای بیشتری است ، پس برگها قسمت اصلی هستند و نتیجه ما به کارهایی که در برگها انجام می شود تبدیل می شود (حالت 1). اگر کارهایی که در برگ و ریشه انجام می شود به صورت یکسان باشد ، نتیجه کار ما با کارهایی که در هر سطح انجام می شود ضرب می شود (حالت 2). اگر کارهایی که در ریشه انجام می شوند بیشتر از لحاظ غیرمتعارف باشند ، نتیجه ما به کارهایی در ریشه انجام می شود (حالت 3).

قضیه اصلی
قضیه اصلی

حالت‌های ناپذیرفتنی[ویرایش]

معادلات زیر را نمی‌توان با استفاده از قضیهٔ اصلی حل کرد:

a مقدار ثابت نیست.

اختلاف بین (f(n و غیر چندجمله‌ای است.

a<۱ است درحالی که نمی‌توان کم تر از یک زیر مسئله داشت.

:

(f(n مثبت نیست.


صحت قضیه اصلی[ویرایش]

نشان دادن درست بودن این قضیه در حالت کلی کار ساده ای نیست اما در ادامه صحت این قضیه را برای یک حالت خاص بررسی می کنیم.

فرض می کنیم (f(n تابعی از مرتبه چندجمله ای باشد یعنی (f(n) = Θ(nd آنگاه :

پس داریم :

logb a > d −→ T(n) = Θ(nlogbb a)

logb a = d −→ T(n) = Θ(nlog a)

logb a < d −→ T(n) = Θ(nd)


میخواهیم مجموع هزینه ها را به دست بیاوریم پس درخت بازگشت آن را رسم میکنیم. برای هر سطح در درخت هزینه های زیر را داریم :

هزینه ی رأسها در سطح ۱:

هزینه ی رأسها در سطح ۲:

...

هزینه ی رأسها در سطحi :

برای محاسبه هزینه کل ، هزینه های هر سطح را با هم جمع میزنیم.( تحلیل سرشکن )

مقدار رأس ریشه در درخت برابرnd  است. به جز راسهای برگ ، هر رأس در این درختa  فرزند دارد که مقدار هرکدامb )-d ) برابر مقدار پدرش است؛ یعنی به عنوان مثال فرزندان ریشه مقداری برابر  دارند. و هزینهی هر برگc است.  

با محاسبه جمع مقادیر سطوح مختلف درخت به مجموع کل میرسیم:

که این مقدار هزینهی متناظر با ریشه (T(n است را تعیین میکند.

قضیه اصلی برای تفریق و حل بازگشتی[۱][ویرایش]

قضیه اصلی واکاوی الگوریتم‌ها برای تعیین کارکردهای دارای محدودیت بالایی Big - O استفاده می شود ، که می تواند در مسایل فرعی شکسته شود. قضیه اصلی برای تکرار تفریق و تقسیم: بگذارید T (n) تابعی باشد که مطابق شکل زیر در n مثبت نشان داده شده است:


قضیه اصلی برای تفریق و حل بازگشتی:

قضیه اصلی برای منها کردن
قضیه اصلی برای منها کردن

فرض کنید T (n) تابعی باشد که مطابق شکل در n مثبت نشان داده شده است:

1. If a<1 then T(n) = O(nk)

2. If a=1 then T(n) = O(nk+1)

3. if a>1 then T(n) = O(nkan/b)

تحلیل زمانی چند الگوریتم[ویرایش]

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

مساله حاصلضرب دو عدد[ویرایش]

در ابتدا الگوریتم متداول برای حاصلضرب دو عدد را در نظر میگیریم. در این الگوریتم هر کدام ازn  درایه ازx  درn درایهy  ضرب می شود . واضح است که زمان اجرای این الگوریتم از مرتبهی است .

همان طور که گفتیم در این بخش برای بهینه کردن مسأله ،الگوریتمهای دیگری معرفی کنیم. برای به دست آوردنحاصلضرب ، از روش تقسیم و حل استفاده میکنیم. مطابق زیر هر عددn  رقمی را به دو بخش ۲n رقمی تقسیم میکنیم:

حاصلضربx  وy  را میتوان به صورت زیر بازنویسی کرد:


Algorithm 1 : Multiply

function Multiply(x,y) n ← size of x aL ← left half digits of x aR ← right half digits of x bL ← left half digits of y bR ← right half digits of y [if number of digits of x or y is odd then add a 0 in begining of it(x or y)]

p1 ← Multiply(aL,bL) p2 ← Multiply(aL,bR) p3 ← Multiply(aR,bL) p4 ← Multiply(aR,bR)

return 10^n p1+ 10^(n/2)(p2 + p3) + p4


میتوان ابتدا هر کدام از حاصلضربهای سمت راست تساوی بالا را به صورت بازگشتی میتوان انجام داد و سپس بااستفاده از نتایج به دست آمده حاصلضرب مورد نظر را به دست آورد.

حال اگر تغییر متغیرهای زیر را در نظر بگیرید:

(p۱ = a · c , p۲ = b · d , p۳ = (a + b)(c + dحاصلضربx · y  را به صورت زیر میتوان بازنویسی کرد:

                                                            

با نوشتن معادله بازگشتی روشن میشود که این روش نسبت به روش قبل زمان اجرای کمتری دارد. در مرحلهی تقسیم مسأله به سه زیر مسأله، هر کدام به اندازهی (T(n۲ تقسیم میکنیم و هزینهی مرحلهی ادغام (Θ(n است، پس معادلهبازگشتی آن به صورت زیر است:

                                                                            


Algorithm 2 : Multiply
function Multiply(x,y) n ← size of x if n = 1 then return x.y aR ← right half digits of x aL ← left half digits of x bR ← right half digits of y bL ← left half digits of y [if number of digits of x or y is odd then add a 0 in begining of it(x or y)]
p1 ← Multiply(aL,bL) p2 ← Multiply(aR,bR) p3 ← Multiply(aL + bL,aR + bR)
[until this line is same as privious algorithm]
 return 

مساله حاصلضرب دو ماتریس[ویرایش]

اگر با الگوریتم متداول یک ماتریسn × n  مانندx  را در یک ماتریسn × n  مانندy  ضرب کنیم هزینه ضرب از مرتبه است .

برای این کار به روش تقسیم، هر ماتریسn × n  را به چهار زیرماتریس به شکل زیر تقسیم میکنیم:

با استفاده از تغییر متغیرهای زیر میتوانیم الگوریتم را بازنویسی کنیم:

T(n) = ۸T(n۲) + θ(n۲) =⇒ T(n) = θ(n۳)

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

معادله ی بازگشتی به صورت زیر میشود:

                                                     T(n) = ۷T(n) + Θ(n۲)       ⇒      T(n) = Θ(nlog۷۲)


واضح است که جواب این معادله از مرتبه زمانی T(n) = ۷T(n) + Θ(n۲)     است.

میخواهیم در یک آرایه مرتب ، عدد خاصی را بیابیم. اولین روش آن است که تمام آرایه را بپیماییم که از مرتبهn است. حال میخواهیم روشی را معرفی کنیم که بتواند با زمان کمتری این کار را انجام دهد.

جستوجوی دودویی[ویرایش]

ورودی: آرایهی مرتب(A = ⟨a1,a2,...,an و کلیدkey

خروجی: اندیسi ، به طوری کهA[i] = key . درصورتی که هیچi ای یافت نشد 1− برگرداند.

میخواهیم در یک آرایه مرتب ، کلید خاصی را بیابیم. اولین روش آن است که تمام آرایه را بپیماییم که از مرتبهn است. در الگوریتمی که در ادامه توضیح داده شده است این کار را با مرتبه زمانی کمتری انجام می دهد. از روش تقسیم استفاده میکنیم یعنی آرایه را به دو قسمت تقسیم میکنیم و هرکدام را جداگانه در جستوجوی دودویی قرارمیدهیم تاجایی که به جواب برسیم.

Algorithm 3 : Recursive Binary Search

function RecursiveBinarySearch(A,key,low,high)

if high < low then


return else

if key < A[mid] then return RecursiveBinarySearch(A,key,low,mid − 1)

else if key > A[mid] then return RecursiveBinarySearch(A,key,mid + 1,high)

return mid

در الگوریتم بعدی جستوجوی دودویی به صورت غیربازگشتی ارایه شده است.

Algorithm 4 : Binary Search
function BinarySearch(A,n,key)
low ← 1n highwhilelowhigh do
if key < A⌊ [mid] then
highmid − 1 else if key > A[mid] then
lowmid + 1
else return mid 
return −1

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  1. Yash Singla (5/16/2020). "Master Theorem For Subtract and Conquer Recurrences". www.geeksforgeeks.org. Check date values in: |تاریخ= (help)