قضیه اصلی در طراحی الگوریتم — به زبان ساده

«قضیه اصلی» یا همان «قضیه مَستر» (Master Theorem) در حوزه «تحلیل الگوریتم‌ها» مطرح می‌شود. در این مقاله به این سوال پاسخ داده شده است که قضیه اصلی در طراحی الگوریتم چیست و چگونه برای حل مسائل بازگشتی به کار گرفته می‌شود.

قضیه اصلی در طراحی الگوریتم چیست ؟

در حیطه «تحلیل الگوریتم‌ها» (Analysis of Algorithms)، قضیه اصلی برای مسائل بازگشتی تقسیم و حل، تحلیل مجانبی (Asymptotic Analysis) را با استفاده از نماد O بزرگ برای انواع رابطه‌های بازگشتی فراهم شده است که در تحلیل بسیاری از الگوریتم‌های تقسیم و حل (Divide and Conquer Algorithms) رخ می‌دهند.

معرفی قضیه اصلی در طراحی الگوریتم

برای مثال می‌توان مسئله‌ای را در نظر گرفت که با استفاده از یک الگوریتم بازگشتی به صورت زیر قابل حل باشد:

procedure p(input x of size n):
if n 
الگوریتم فوق، مسئله را به صورت بازگشتی به تعدادی زیر مسئله (مسئله کوچک‌تر) تقسیم می‌کند. هر زیر مسئله اندازه‌ای برابر با $$ frac n b $$ دارد. درخت راه حل برای هر فراخوانی بازگشتی دارای یک گره (Node) است.
            

                
                    

                        

                            
                        
                        

                            

                                فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته – مرور و تست کنکور ارشد در تم آف
                            
                        
                        

                            
کلیک کنید
                        
                    
                
            
        
فرزندان آن گره سایر فراخوانی‌هایی هستند که به واسطه آن فراخوانی خاص ایجاد شده‌اند. برگ‌های درخت «وضعیت پایه» (Base Case) بازگشت به حساب می‌آیند. برگ‌ها زیرمسئله‌هایی هستند (با اندازه کم‌تر از k) که عملیات بازگشت ندارند. در مثال بالا، هر گره غیر برگ دارای $$ a $$ گره فرزند است.

هر گره متناظر با اندازه زیرمسئله $$ n $$ مقداری کار انجام می‌دهد که به نمونه فراخوانی بازگشتی ارجاع داده و به وسیله $$ f(n) $$ مشخص می‌شود. کل مقدار کار انجام شده به وسیله تمام الگوریتم برابر با مجموع کار انجام شده توسط همه گره‌های درخت است. زمان اجرای یک الگوریتم مثل الگوریتم «p» در بالا با یک ورودی به اندازه «n» که معمولاً با $$ T(n) $$ نشان داده می‌شود را می‌توان به وسیله رابطه بازگشتی زیر نوشت:
$$T(n) = aT( frac n b) + f(n)$$
در رابطه فوق، $$ f(n) $$ مدت زمانی برای ایجاد زیرمسئله‌ها و ترکیب نتایج آن‌ها در عملیات فوق به حساب می‌آید. این معادله می‌تواند به طور متوالی جایگزین خودش شود و جهت دستیابی به یک عبارت برای کل کار انجام شده گسترش داده شود.
            

                
                    

                        

                            
                        
                        

                            

                                فیلم آموزش حل روابط بازگشتی در تم آف
                            
                        
                        

                            
کلیک کنید
                        
                    
                
            
        
قضیه اصلی اجازه می‌دهد تا رابطه‌های بازگشتی بسیاری با این فُرم به طور مستقیم به نماد O بزرگ تبدیل شوند. این کار بدون بسط دادن رابطه بازگشتی انجام می‌شود.
رابطه فوق دارای چند شرط برای مقادیرش است. شروط مقادیر معادله قضیه اصلی به صورت زیر هستند:
$$a geq 1$$
$$b > 1$$
$$f(n) > 0$$
برای مثال می‌توان دو معادله زیر را در نظر گرفت، این دو معادله را می‌توان با استفاده از قضیه اصلی حل کرد:
$$c + T(frac n 2) longrightarrow a=1,‎,b=2,‎‎‎‎‎‎and,f(n)=c,$$
$$c + T(frac n 2) longrightarrow a=2,‎,b=2‎‎,‎‎‎‎‎‎and‎,‎f(n)=n,$$
بسیاری از الگوریتم‌ها دارای پیچیدگی زمانی به صورت قضیه اصلی هستند. برای مثال در بحث زمان اجرای الگوریتم‌ها، می‌توان نشان داد که مرتبه زمانی الگوریتم مرتب‌سازی ادغام (Merge Sort Algorithm) به صورت زیر است:
$$T(n) = 2T(frac n 2) + n$$
به صورت مشابه، روش پیمایش درخت دودویی (Binary Tree Traversal) نیز به مرتبه زمانی به صورت زیر و در فرم قضیه اصلی نیاز دارد:
$$T(n) = 2T(frac n 2) + O(1)$$
در مقایسه $$log _{b}a $$ با رفتار $$f(n)$$ می‌توان به این نتیجه رسید که قضیه اصلی در طراحی الگوریتم راه حل مناسبی برای بیشتر معادلات بازگشتی به شمار می‌رود. پیش از بررسی دقیق‌تر قضیه اصلی در طراحی الگوریتم ، ابتدا بهتر است به ارائه تعریفی از معادله بازگشتی (Recursion) و شرح چیستی آن پرداخته شود.
رابطه بازگشتی چیست؟
رابطه بازگشتی به معنی «تعریف یک مسئله به وسیله خود معادله» است. این روش یک ابزار بسیار قدرتمند در نوشتن الگوریتم‌ها به حساب می‌آید. معادله بازگشتی به این دلیل که در آن نمونه‌های زیادی از عبارات بر حسب خودشان نوشته شده‌اند، کاملاً یک روش ریاضی است.
            

                
                    

                        

                            
                        
                        

                            

                                فیلم آموزش حل روابط بازگشتی در تم آف
                            
                        
                        

                            
کلیک کنید
                        
                    
                
            
        
برای مثال می‌توان دنباله (سری) فیبوناچی (Fibonacci Sequence) را در نظر گرفت که به صورت زیر نوشته می‌شود:
$$ F(i) = F(i-1) + F(i-2) $$

الگوریتم بازگشتی فرآیندی برای پردازش یا حل مسئله‌ای بر اساس (نسخه ساده‌تر) خود مسئله به حساب می‌آید.
            

                
                    

                        

                            
                        
                        

                            

                                فیلم آموزش طراحی الگوریتم در تم آف
                            
                        
                        

                            
کلیک کنید
                        
                    
                
            
        
می‌توان به عنوان مثال ساده‌ای از زندگی روزمره با صورت مسئله «پیدا کردن راه خانه خود» عملیات زیر را برای حل آن در نظر گرفت:

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

در این مثال راه‌حل پیدا کردن مسیر خانه دارای دو یا سه مرحله زیر است:

• شخص به خانه نمی‌رود، چون در حال حاضر در خانه است.
• یک روش بسیار ساده برای حل مسئله در نظر گرفته می‌شود.
• در نهایت کل الگوریتم دوباره انجام می‌شود.

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

شرح قضیه اصلی در طراحی الگوریتم

در ابتدا برای شرح قضیه اصلی در طراحی الگوریتم یک رابطه بازگشتی به شکل زیر در نظر گرفته می‌شود:

$$T(n) = aT(frac n b)$$

در معادله فوق، a تعداد فرزندان هر گره (Node) یعنی همان تعداد زیر مسئله‌ها را نشان می‌دهد و زمان اجرای هر یک از گره‌های اولیه با سه فرزند $$T( frac n b)$$ است.

درخت این معادله $$log _{b}n $$ عمق دارد و عمق i شامل $$a^i$$ گره است. بنابراین، تعداد برگ‌ها (فرزندان) در درخت با معادله $$a^{log _{b}n} = n ^ {log _{b}a}$$ محاسبه می‌شوند و زمان اجرای الگوریتم $$Theta(n ^ {log _{b}a})$$ است.

طبق تصویر فوق و به طور شهودی، قضیه اصلی استدلال می‌کند که اگر تابع مجانبی (Asymptotically) مثبت $$f(n)$$ به این تابع بازگشتی اضافه شود، تابعی به صورت زیر ایجاد می‌شود:

$$T(n) = aT( frac n b) + f(n)$$

می‌توان فرم مجانبی $$T$$ را بر اساس مقایسه نسبی بین $$f$$ و $$log _{b}n $$ تعیین کرد. قضیه اصلی در طراحی الگوریتم دارای حالت‌های گوناگونی است که در بخش بعدی به آن‌ها پرداخته می‌شود.

حالت‌های قضیه اصلی در طراحی الگوریتم

قضیه اصلی در طراحی الگوریتم دارای سه حالت گوناگون زیر است که برای حل هر مسئله یکی از این سه حالت انتخاب می‌شود:

• حالت اول: اگر معادله $$f(n)=O(n ^ {log _{b}a-epsilon})$$ برای $$epsilon>0$$ برقرار باشد، آن‌گاه زمان زیر برای رابطه برقرار است:

$$T(n)=Theta(n ^ {log _{b}a})$$

• حالت دوم: اگر معادله $$f(n)=Theta(n ^ {log _{b}a})$$ برقرار باشد، آن‌گاه زمان زیر برای رابطه برقرار است:

$$T(n)=Theta(n ^ {log _{b}a}lg,n )$$

• حالت سوم: اگر معادله $$f(n)=Omega(n ^ {log _{b}a+epsilon})$$ برای $$epsilon>0$$ و اگر $$af(n/b) leq cf(n)$$ برای $$c

$$T(n)=Theta(f(n))$$

با استفاده از این سه حالت، می‌توان به راحتی پاسخ معادله بازگشتی به فرم $$T(n) = aT( frac n b) + f(n)$$ را به دست آورد. در بخش بعدی این مقاله به بررسی ایده‌ای پرداخته می‌شود که باعث ایجاد قضیه اصلی در طراحی الگوریتم شد.

ایده پشت پرده قضیه اصلی در طراحی الگوریتم چیست ؟

ایده‌ای که باعث ایجاد قضیه اصلی در طراحی الگوریتم شد و در پشت پرده آن قرار دارد بر اساس مقایسه $$n ^ {log _{b}a}$$ با تابع $$f(n)$$ است.

به صورت کلی می‌توان گفت که قضیه اصلی در طراحی الگوریتم بر اساس مقایسه ایجاد می‌شود. به اصطلاح عامیانه، قضیه اصلی اساساً به دنبال این موضوع است که بین $$f(n)$$ و $$n ^ {log _{b}a}$$ کدام یک بر دیگری تسلط دارد. برای ساده و بهتر متوجه شدن سه حالت بخش قبل، سه حالت زیر ارائه شده است:

• حالت اول: اگر تابع $$f(n)$$ تحت سلطه (کوچکتر از) $$n ^ {log _{b}a}$$ باشد، آن‌گاه رابطه پیچیدگی زمانی زیر برقرار است:

$$T(n)=Theta(n ^ {log _{b}a})$$

طبق حالت اول بخش پیشین، در معادله $$f(n)=O(n ^ {log _{b}a-epsilon})$$ به عنوان بدترین حالت $$f(n)$$، معادله $$n ^ {log _{b}a-epsilon}$$ در نظر گرفته می‌شود که کمتر از $$n ^ {log _{b}a}$$ است. بنابراین، $$n ^ {log _{b}a}$$ زمان بیشتری می‌برد و در نتیجه تسلط پیدا می‌کند.

• حالت دوم: اگر $$f(n)$$ و همچنین $$n ^ {log _{b}a}$$ هر دو به یک اندازه وجود داشته باشند (برابر باشند). بنابراین زمانی که صرف این حالت می‌شود برابر با رابطه زیر است:

$$T(n)=Theta(n ^ {log _{b}a}lg,n )$$

• حالت سوم: طبق حالت سوم بخش پیشین، بهترین حالت $$f(n)$$ برابر با $$n ^ {log _{b}a-epsilon}$$ به حساب می‌آید. بنابراین، بهترین حالت $$f(n)$$ بزرگتر از $$n ^ {log _{b}a}$$ است و از این رو $$f(n)$$ زمان بیشتری می‌برد و در نتیجه تسلط پیدا می‌کند (بزرگتر می‌شود). در نهایت می‌توان گفت که زمان رابطه در این حالت به صورت زیر است:

$$T(n)=Theta(f(n))$$

در بخش بعدی این مقاله به شرح قضیه اصلی در طراحی الگوریتم به وسیله درخت بازگشتی پرداخته می‌شود.

تعریف قضیه اصلی در طراحی الگوریتم به وسیله درخت بازگشتی

قضیه اصلی در طراحی الگوریتم عمدتاً از روش درخت بازگشتی استفاده می‌کند. اگر درخت بازگشتی $$T(n) = aT( frac n b) + f(n)$$ طراحی شود، تابع $$f(n)$$ در ریشه درخت قرار می‌گیرد و برگ‌های آن با $${log _{b}a}$$ محاسبه می‌شوند و ارتفاع درخت را $${log _{b}n}$$ نشان می‌دهد.

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

اگر کار انجام شده در برگ‌ها و ریشه به طور مجانبی (Asymptotically) یکسان باشند، نتیجه ضرب ارتفاع در کار انجام شده در هر سطح است و این روش حالت دوم را نشان می‌دهد. اگر کار انجام شده در ریشه به طور مجانبی بیشتر باشد، نتیجه مسئله کار انجام شده در ریشه است و این روش حالت سوم را نشان می‌دهد.

تا به این بخش از مقاله مطالبی که ارائه شدند مبتنی بر $$n ^ {log _{b}a}$$ بودند، با این که $$T(n)$$ برای قضیه اصلی در طراحی الگوریتم به وسیله $$f(n)$$ و $$T( frac n b)$$ ایجاد شده است.

چرا از $$n ^ {log _{b}a}$$ برای قضیه اصلی در طراحی الگوریتم استفاده می‌شود؟

همان‌طور که در بخش‌های قبلی ارائه شد معادله زیر نشان دهنده قضیه اصلی در طراحی الگوریتم است:

$$T(n) = aT(frac n b) + f(n)$$

در رابطه فوق، عبارت $$aT( frac n b)$$ در نظر گرفته می‌شود و $$T(n)’$$ زمان صرف شده توسط این عبارت به حساب می‌آید. عبارت $$aT( frac n b)$$ به معنی این است که مسئله با اندازه $$n$$ به $$a$$ زیر مسئله دیگر یا بیشتر با سایز $$frac n b$$ تقسیم می‌شود.

بنابراین، زمان کامل صرف شده برای اندازه $$n$$ یعنی $$T(n)’ = a‎; times ‎;T( frac n b) + f(n)$$ و $$T( frac n b)$$ زمانی است که به وسیله هر زیر مسئله با سایز $$frac n b$$ به دست می‌آید. بنابراین زمان کامل رابطه برابر است با:

$$T(n)’=aT( frac n b)$$

برای تجزیه و تحلیل عبارت $$T( frac n b)$$، اندازه آن به طور مجدد به $$a$$ زیر مجموعه یا بیشتر با اندازه $$frac n {b^2}$$ تقسیم می‌شود. از این رو، عبارت زیر ایجاد خواهد شد:

$$T( frac n b)=aT(frac n {b^2})$$

$$implies‎: T(n)’=aT( frac n b)=a^2T(frac n {b^2}) $$

پس می‌توان به راحتی نوشت:

$$T(n)’=aT( frac n b)=a^2T(frac n {b^2})=a^3T(frac n {b^3})=a^iT(frac n {b^i})$$

بنابراین می‌توان بیان کرد که کل زمان صرف شده برای عبارت $$aT( frac n b)$$ مقدار $$a^iT(frac n {b^i})$$ است. در مرحله بعد عبارت زیر در نظر گرفته می‌شود:

$$n=b^k implies‎: k=log _{b}n$$

در سطح i، اندازه هر زیر مسئله $$frac n {b^i}$$ به حساب می‌آید. در آخرین سطح، اندازه زیر مسئله برابر با عدد یک است. یعنی:

$$frac n {b^i}=1 implies‎: n={b^i} implies‎: log _{b}n=i=k implies‎: i=k $$

با استفاده از عبارت فوق می‌توان $$T(n)’=$$ را بازنویسی کرد. عبارات زیر این بازنویسی را نشان می‌دهند:

$$T(n)’=a^iT(frac n {b^i})=a^{log _{b}n} {(frac {b^i} {b^i})}(n=b^k=b^i)$$

$$=a^{log _{b}n}(T(1))$$

$$=Theta(a^{log _{b}n})=Theta(n^{log _{b}a})$$

بدین ترتیب، مشاهده می‌شود که عبارت اول زمانی برابر با $$Theta(n^{log _{b}a})$$ صرف می‌کند و به همین دلیل است که با $$f(n)$$ مقایسه می‌شود. بنابراین مفهوم قضیه اصلی در طراحی الگوریتم تا به اینجا مورد بررسی قرار گرفت و دلیل استفاده از $$n^{log _{b}a}$$ برای مقایسه در آن نیز شرح داده شد.

حالت‌های غیر قابل قبول برای قضیه اصلی در طراحی الگوریتم

برخی از معادلات به وسیله قضیه اصلی در طراحی الگوریتم قابل حل نیستند. در این بخش این معادلات ارائه شده‌اند:

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

$$T(n) = 2^nT(frac n 2) + n^n$$

• برای حل معادلات به وسیله قضیه اصلی باید تعداد زیر مسئله‌ها ثابت باشند، $$a$$ در معادله زیر ثابت نیست. پس در معادلاتی به فرم زیر از قضیه اصلی نمی‌توان استفاده کرد:

$$T(n) = 2T(frac n 2) + frac n {log _{}n}$$

• معادلات دارای تفاوت غیر چندجمله‌ای (Non Polynomial) مابین $$f(n)$$ و $$n^{log _{b}a}$$ به وسیله قضیه اصلی در طراحی الگوریتم قابل حل نیستند:

$$T(n) = 0.5T(frac n 2) + n$$

• معادلاتی که به وسیله قضیه اصلی حل می‌شوند، نمی‌توانند کمتر از یک زیر مسئله داشته باشند ($$a

$$T(n) = 64T(frac n 8) – n^2{log _{}n}$$

• در معادلاتی که $$f(n)$$ مثبت نیست، نمی‌توان از قضیه اصلی استفاده کرد:

$$T(n) = T(frac n 2) + n(2 – cos:n)$$

پس از شرح مفاهیم قضیه اصلی در طراحی الگوریتم ، اکنون در ادامه نمونه‌ها و مثال‌هایی از قضیه اصلی برای یادگیری روش استفاده از آن ارائه شده است.

مثال‌های استفاده از قضیه اصلی در طراحی الگوریتم

در این بخش برای یادگیری بهتر و تفهیم قضیه اصلی در طراحی الگوریتم چند مثال همراه با راه‌حل آن‌ها ارائه شده است.

مثال قضیه اصلی در طراحی الگوریتم : مرتب‌سازی ادغام

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

$$T(n) = 2T(frac n 2) + n$$

در این مثال مقادیر زیر وجود دارند:

$$a=2$$

$$b=2$$

$${log _{b}a} = log _{2}2 = 1$$

حال در ادامه دو عبارت زیر از رابطه قضیه اصلی با همان عبارات از مثال فوق برابر قرار می‌گیرند:

$$n^{log _{b}a} = n^{log _{2}2} = {n}$$

$$f(n)=n$$

$$implies‎: n^{log _{b}a} = {n} = f(n)$$

با مقایسه $$n^{log _{b}a}$$ با $$f(n)$$ به نتیجه زیر می‌توان رسید:

$$implies‎: f(n)=Theta(n^{log _{b}a})$$

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

$$T(n)=Theta(n ^ {log _{b}a}lg,n ) = Theta(n‎:lg‎:n)$$

مثال قضیه اصلی در طراحی الگوریتم : پیمایش درخت دودویی

به طور مشابه با مثال اول، راه‌حل پیمایش درخت دودویی با رابطه زیر به وسیله قضیه اصلی در طراحی الگوریتم ایجاد می‌شود.

$$T(n) = 2T(frac n 2) + O(1)$$

$$f(n)=O(1)$$

چون $${n^{log _{b}a}}={n}$$، بزرگتر از مقدار ثابت $$a$$ است، بنابراین قضیه اصلی با حالت اول، پاسخ این مثال را به دست می‌آورد:

$$T(n)=Theta(n ^ {log _{b}a}) = Theta(n‎)$$

مثال قضیه اصلی در طراحی الگوریتم : حل یک رابطه

• حل رابطه زیر با استفاده از قضیه اصلی در طراحی الگوریتم در ادامه ارائه شده است:

$$T(n) = 2T(frac n 2) + n^2$$

ابتدا مقادیر این عبارت استخراج می‌شوند:

$$a=2$$

$$b=2$$

$${log _{2}2} = 1$$

$$implies‎: n^{log _{b}a} = {n^1} = n$$

عبارات معادله برابر با همان عبارت در رابطه قضیه اصلی قرار می‌گیرند:

$$f(n)=n^2$$

همچنین، با مقایسه $$n^{log _{b}a}$$ و $$f(n)$$ به نتیجه زیر می‌توان رسید:

$$implies‎: f(n)=Omega(n^{1+epsilon}):(epsilon=1)$$

اگر بقیه شرایط حالت سوم برای $$f(n)$$ برآورده شوند، این حالت در این سوال قابل اعمال است. شرط $$af(n/b) leqslant cf(n)$$ در این مثال برای $$c

بنابراین برای یک n، عبارت زیر نوشته می‌شود. برای $$(c=frac 1 2)$$:

$$af(frac n b) = 2f(frac n 2) = 2frac {n^2} 4 = frac {n^2} 2 leq frac 1 2(n^2) : $$

بنابراین، شرط برای $$(c=frac 1 2)$$ برقرار است و پاسخ نهایی به صورت زیر نوشته می‌شود:

$$T(n)=Theta(f(n)) = Theta(n^2‎)$$

مثال چهارم استفاده از قضیه اصلی در طراحی الگوریتم

معادله زیر با روش قضیه اصلی در طراحی الگوریتم حل می‌شود:

$$T(n) = 2T(frac n 2) + sqrt []{n}$$

مقادیر رابطه بالا به صورت زیر است:

$$a=2$$

$$b=2$$

$${log _{2}2} = 1$$

$$implies‎: n^{log _{b}a} = {n^1} = n$$

با جایگذاری عبارت این مثال رابطه قضیه اصلی پاسخ زیر به دست می‌آید، این مثال به وسیله حالت دوم قضیه اصلی حل شده است:

$$f(n) = sqrt []{n}$$

$$implies‎: f(n) = Theta(n^{1-epsilon})$$

$$implies‎: T(n) = Theta(n)$$

مثال پنجم استفاده از قضیه اصلی در طراحی الگوریتم

رابطه زیر در نظر گرفته شده است و با قضیه اصلی بررسی می‌شود:

$$T(n) = 3T(frac n 4) + n‎:lg‎:n$$

مقادیر استخراج شده از این مثال به صورت زیر هستند:

$$a=3$$

$$b=4$$

$${4log _{4}3} = 0.792$$

$$f(n)$$ به صورت زیر جایگذاری می‌شود و این مثال حالت سوم از قضیه اصلی را نشان می‌دهد:

$$f(n) = Omega(n^{log _{4}3+epsilon})$$

برای $$(c=frac 3 4)$$:

$$3(frac n 4):lg:(frac n 4) leq frac 3 4n:lg:n = c:ast:f(n)$$

$$implies‎: T(n) = Theta(n:lg:n)$$

مثال ششم استفاده از قضیه اصلی در طراحی الگوریتم

معادله‌ای که برای این مثال بررسی می‌شود، به صورت زیر است:

$$T(n) = 2T(frac n 2) + n‎:lg‎:n$$

مقادیر معادله فوق در ادامه نشان داده شده‌اند:

$$a=2$$

$$b=2$$

$${log _{2}2} = 1$$

$$implies‎: n^{log _{b}a} = {n^1} = n$$

$$f(n)$$ این مثال به صورت زیر است:

$$f(n) = n‎:lg‎:n$$

$$f(n)$$ باید چندجمله‌ای با ضریب $$n^epsilon$$ باشد، اما در این مثال چندجمله‌ای است که با ضریب $$lg:n$$ بزرگ‌تر در نظر گرفته می‌شود. بنابراین، قضیه اصلی در این مثال اعمال نمی‌شود.

مثال هفتم استفاده از قضیه اصلی در طراحی الگوریتم

رابطه مورد بررسی قرار گرفته در این سوال به صورت زیر است:

$$T(n) = 2T(sqrt []{n}) + lg:n$$

رابطه ارائه شده در این مثال به فرم $$aT( frac n b) + f(n)$$ نیست، پس به صورت مستقیم نمی‌توان قضیه اصلی را روی آن اعمال کرد.

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

$$lg:n = m implies‎: n=2^m$$

با جایگزاری $$n$$ با $$n=2^m$$، معادله به فرم زیر تبدیل می‌شود و باید ساده شود تا بتوان آن را با قضیه اصلی حل کرد:

$$T(2^m) = 2T(2^{m/2})+m$$

در این مرحله $$S(m)$$ جایگزین $$T(2^m)$$ می‌شود:

$$implies‎: S(m) = 2S(frac m 2)+m$$

اکنون، این رابطه فرم قضیه اصلی را دارد و دقیقا همان رابطه‌ای است که در مثال اول بررسی شد. پس در روش حل آن روشن است که:

$$S(m) = O(m:lg:m)$$

$$implies‎: T(n) = T(2^m) = S(m) = O(m‎:lg‎:m)$$

در نهایت برای رسیدن به پاسخ صحیح، مقدار $$m$$ با $$lg:n$$ جایگزین شده است و رابطه زیر ایجاد می‌شود:

$$implies‎: T(n) = O(lg‎:n:lg(lg:n))$$

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

مفهوم ساختمان داده و طراحی الگوریتم

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

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

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

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

جمع‌بندی

در این مقاله، مفهوم و ایده کلی قضیه اصلی در طراحی الگوریتم مورد بحث قرار گرفت. همچنین روش بازگشتی، روش‌های گوناگون شرح روابط قضیه اصلی، زمان رابطه‌ها به وسیله آن و بررسی مثال‌هایی نیز برای درک بهتر این روش ارائه شدند.

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