نوشته های دانا میرافضل

الگوریتم های بازگشتی و بررسی پیچیدگی آنها

دانا میرافضل — Wed, 01 Dec 2021 14:45:23 +0330

این نوشته یک بازگردان فارسی از Computational Complexity Part Two منتشر شده توسط misof در وبسایت topcoder.com است. در ترجمه مطلب تلاش شده تا بهترین واژه ها جایگزین شود و نوشتار به گونه ای باقی بماند که امانت ترجمه حفظ شده و همزمان برای خواننده قابل فهم و درک باشد هرچند در طول متن ممکن است مواردی چندان واضح نباشد که خب به علت پیچیدگی نسبی برای کسی که از قبل با مباحث مطرح شده آشنایی ندارد در خود مقاله اصلی شاید بعضی بخش ها نیاز به خوانش چند باره داشته باشند. موضوع بحث بررسی پیچیدگی الگوریتم های بازگشتی در علوم کامپیوتر است و بدین منظور مراجعاتی به دانش ریاضی نیز صورت گرفته. در صورتی که پیشنهادی برای بهتر شدن ترجمه دارید از بخش نظرات با من در میان بگذارید.بخش هایی که داخل [ ] آمده اند نوشته مترجم برای شفاف سازی منظور یا ارائه توضیحات مربوط به بحث در آن مقطع است.اصل مقاله را میتوانید از طریق لینک زیر مطالعه بفرمایید: https://www.topcoder.com/thrive/articles/Computational%20Complexity%20part%20two دلیل انتخاب درخت برای تصویر این نوشته مربوط به یک متد بررسی پیچیدگی توابع بازگشتی است که در ادامه می خوانیددر این بخش مقاله[ مقاله در دو بخش نوشته شده که بخش اول آن مربوط به معرفی مفهوم پیچیدگی الگوریتم ها و مبانی آنهاست که از اینجا میتوانید بخوانید] ما روی تخمین پیچیدگی زمانی برنامه های بازگشتی توجه می کنیم. طبیعتا این کار منجر به یافتن ضریب رشد[order of growth در اینجا ضریب رشد ترجمه شده] برای جواب ها یک معادله بازگشتی خواهد شد. اگر دقیقا نمی دانید که جواب بازگشتی چیست ،نگران نباشید، آن را در مکان درست و در زمان درست توضیح خواهیم داد، اما در ابتدا ما یک کیس ساده تر را بررسی میکنیم- برنامه های بدون بازگشت.حلقه های تو در تودر ابتدا اجازه دهید برنامه های ساده که توابع را صدا نمیزنند بررسی کنیم. قانون کاربردی برای پیدا کردن پیچیدگی الگوریتم چنین برنامه ای اینچنین است :تخمین بزنید که هر حلقه حداکثر چند بار میتواند اجرا شود.جواب را برای حلقه هایی که بعد از یکدیگر می آیند جمع بزنید.جواب را برای حلقه های تو در تو داخل کد در هم ضرب کنید. [برای مثال اگر یک حلقه با n بار تکرار دارید که داخل آن حلقه دیگری با 2n بار تکرار وجود دارد باید آن ها را در هم ضرب کنید و به n*2n=2n^2 برسید.]مثال 1: تخمین پیچیدگی زمانی یک تکه کد تصادفی :int result = 0; // 1 for (int i = 0; i < N; i++) // 2 for (int j = i; j < N; j++) { // 3 for (int k = 0; k < M; k++) { // 4 int x = 0; // 5 while (x < N) { result++; x += 3; } // 6 } // 7 for (int k = 0; k < 2 * M; k++) // 8 if (k % 7 == 4) result++; // 9 } // 10پیچیدگی زمانی حلقه While در خط ششم واضحا از مرتبه n ام ( O(n) ) است( از آنجایی که قطعا بیشتر از N/3 +1 بار اجرا نخواهد شد.[ توضیحات مترجم : چون پرش ها در متغیر iterator یعنی x در هر مرحله 3 واحد است-خط هشت ] )حالا به حلقه های for در خطوط 4تا7 دقت کنید. واضح است متغیر k ، به تعداد M دفعه افزایش پیدا میکند و هر دفعه حلقه while خط 6 اجرا می شود بنابراین کل پیچیدگی خطوط 4 تا 7 از مرتبه O(M*N) است.پیچیدگی زمانی حلقه for خطوط 8تا9 از مرتبه O(M) است; بنابراین پیچیدگی زمانی خطوط 4 تا 9 از مرتبه MN+M یعنی O(MN) است.[ با فرض اینکه N متغیر اصلی مسئله است خط (شیبدار صعودی) همواره رشد بیشتری نسبت به ثابت ( که البته خود ثابت هم خط افقی است) دارد و در مقادیر بزرگ M قطعا MN غالب خواهد بود].بخش داخلی از مرتبه O(N^2) بار اجرا خواهد شد-یک بار برای هر ترکیب i و j.(توجه کنید کل در کل N(N+1)/2 حالت برای i و j وجود دارد ولی بدون در نظر گرفتن ثابت ها و حذف جملات با رشد کمتر در بینهایت ، جواب در نهایت از مرتبه N^2 است.)از موارد بالا میتوان نتیجه گرفت که پیچیدگی زمانی الگوریتم بالا از مرتبه MN*N^2 یعنی O(MN^3) است.از اینجا به بعد تصور میکنیم که خواننده توانایی این را دارد که time complexity الگوریتم های ساده را به روشی که در بالا نشان داده شد تقریب بزند. حالا برنامه هایی با بازگشت را در نظر میگیرم(هنگامی که یک تابع خودش را گاها با پارامتر های مختلف صدا بزند) و تلاش می کنیم که تاثیر این بازگشت ها را روی پیچیدگی زمانی این توابع بررسی کنیم.استفاده از بازگشت برای ایجاد اشیاء ترکیبییکی از کاربرد های بازگشت پیاده سازی الگوریتم های backtracking به منظور تولید تمام جواب های ممکن برای یک مسئله است. ایده کلی ایجاد تمام پاسخ های ممکن بصورت فزاینده است و در نهایت بازگشت به عقب پیدا کردن یک راه دیگر هنگامی که تمامی جواب های یک شاخه ناموفق هستند.این رویکرد کاملا همه جانبه نیست و مسائلی وجود دارند که غیر ممکن است که همه جواب ها را بصورت افزایشی تولید کرد ، هر چند خیلی اتفاق می افتد که مجموعه تمام جواب های قابل قبول یک مسئله با یک مجموعه اشیاء ترکیبی یک ریخت متناسب است. اغلب آن مجموعه ، مجموعه همه جایگشت ها(با طول مشخص)است . اما سایر اشیاء(ترکیب ها[توضیح مترجم: جایگشت ها ترکیباتی از یک سری اشیاء هستند که ترتیب در آنها اهمیت دارد. یعنی تغییر ترتیب قرار گیری اشیاء خود یک جایگشت جدید ایجاد می کند] ، اجزا و … ) نیز به گاها دیده می شود.به عنوان نکته جانبی ، همواره میتوان تمام ترکیب صفر و یک را ایجاد کرد و تک تک آن ها را آزمود(یعنی بررسی کرد که آیا در مسئله صدق می کنند) و بهترین پاسخ را نگاه داشت. اگر ما بتوانیم برای بهترین جواب از بالا یک مرز پیدا کنیم آنگاه این روش محدود و متنهایست. هر چند این رویکرد اصلا سریع نیست. از این روش استفاده نکنید مگر اینکه هیچ روش دیگری وجود نداشته باشد.مثال 2: یک الگوریتم نه چندان قوی برای برای ساختن تمام جایگشت های ارقام 0 تا n-1 :vector permutation(N); vector used(N, 0); void try (int which, int what) { // try taking the number “what” as the “which”-th element permutation[which] = what; used[what] = 1; if (which == N - 1) outputPermutation(); else // try all possibilities for the next element for (int next = 0; next < N; next++) if (!used[next]) try (which + 1, next); used[what] = 0; } int main() { // try all possibilities for the first element for (int first = 0; first < N; first++) try (0, first); }در این مثال یک کف نه چندان نزدیک برای پیچیدگی زمانی الگوریتم تعداد پاسخ های ممکن است.الگوریتم های عقب روند [منظور همان الگوریتم های بازگشتی است.] معمولا برای حل کردن مسائل دشوار استفاده می شوند( برای مثال هنگامی که ما نمی دانیم که راه حلی که بطور قابل توجه بهینه تر باشد وجود دارد یا خیر؟ پاسخ های ممکن برای مسائل اینچنینی و در نتیجه پیچیدگی زمانی آنها معمولا رشد نمایی (یا حتی بدتر) دارند.با روش تقسیم و حل [ ترجمه اصطلاح Divide and conquer در طراحی الگوریتم به معنی بخش بخش کردن مسئله و حل مستقل هر کدام از بخش ها و در نهایت پیوستن جواب هاست که تکنیکی رایج در حل مسائل است.]از مثال قبلی این احساس به ما منتقل شد که بازگشت کند است و به ساخت برنامه های آهسته و کند می انجامد. دقیق برعکس است.بازگشت میتواند یک روش خیلی قدرتمند برای طراحی الگوریتم های کارآمد باشد. راه معمول برای ساخت برنامه های بازگشتی کارآمد و بهینه استفاده از الگوی "تفرقه اندازی و غلبه" است-تلاش میکنیم مسئله را به بخش های کوچکتر و مستقل تبدیل کنیم. هر بخش را بطور جداگانه حل می کنیم.در نهایت پاسخ ها در هر بخش را کنار هم قرار میدهیم تا به پاسخ مسئله برسیم. لزومی ندارد که اشاره کنیم "هر بخش را بطور جداگانه حل میکنیم" توسط بازگشت انجام می شود و کوچک کردن مداوم مسئله تا به یک بخش قابل حل برسیم توسط brute-force انجام می شود.[توضیح مترجم: تکنیک brute-force عملا معنی تلاش چندین و چند باره را می دهد که توسط حلقه ها انجام می شود.]مثال 3: کد زیر الگوریتم مرتب سازی MergeSort را [در منابع فارسی به آن با نام مرتب سازی ادغامی نیز اشاره شده] در فرمت سودو کد نشان میدهد:کد زیر الگوریتم مرتب سازی MergeSort را [در منابع فارسی به آن با نام مرتب سازی ادغامی نیز اشاره شده] در فرمت شبه کد نشان میدهد:MergeSort(sequence S) { if (size of S <= 1) return S; split S into S_1 and S_2 of roughly the same size; MergeSort(S_1); MergeSort(S_2); combine sorted S_1 and sorted S_2 to obtain sorted S; return sorted S; }واضح است که زمان O(N) برای شکستن یک آرایه N عضوی به دو آرایه کافی است.( بسته به نحوه پیاده سازی اینکار حتی میتواند در زمان ثابت یعنی O(1) نیز انجام شود.) ادغام کردن دو آرایه مرتب شده کوچکتر میتواند در O(n)[در اینجا نویسنده از تتا استفاده کرده-به درستی هم استفاده کرده اما برای سادگی من اکثر نماد ها رو در ترجمه از همان Big-Oh استفاده میکنم که هم سر شما در نیاد برای محاسبات ریاضیش هم اینکه درستی مطلب هم دست نخورده باقی میمونه][ توضیح در مورد پاراگراف بالا : برای MergeSort کردن یک آرایه ما اون رو به دو آرایه کوچک تقسیم میکنیم بعد خود اون دو تا رو Mergesort میکنیم ( که البته چجوریش خودش مهمه ، ما هنوز روش دقیقی برای Mergesort نگفتیم به شما) و در نهایت اون دو آرایه مرتب شده رو ادغام میکنیم به جوری که حاصل نیز مرتب باشه. زمانی که دو تا آرایه روی هم N عنصر داشته باشن برای مرتب شدن طبق گفته نویسنده پیچیدگی زمانی ادغام این دو تا از مرتبه N هست. توجه کنید که صرفا کنار هم نمیزاریمشون بلکه عناصر هر کدوم باید نسبت به اون یکی هم در خروجی مرتب باشن برای همین O(1) نیست پیچیدگیش. چجوری ادغام دو آرایه مرتب و دلیل اینکه پیچیدگی مرتبه N داره در ادامه متن اومده. ]آرایه خالی S رو در نظر بگیرید که ادغام شده S1 و S2 باشد. در هر لحظه عنصر بعدی که باید توی S قرار داده شود عنصر اول S1 یا عنصر اول S2 است. این دو عنصر را مقایسه کنید ، عنصر کوچکتر را در انتهای S قرار دهید و از آرایه کوچکتری که متعلق به آن است حذف کنید. اگر این کار را n-1 بار تکرار کنید در نهایت به آرایه کامل مرتب شده و ادغامی S1 و S2 یعنی S می رسید.در نتیجه زمان کلی ادغام کردن یک آرایه با N عنصر از مرتبه O(n) است + زمانی صدا زدن تابع بازگشتی برای دو بخش مجزا.[ توضیح مترجم : جمله بالا می گوید : برای اینکه یک سری اعداد با N عضو را مرتب سازی کنیم زمان کلی مصرف شده زمانی هست که ما این دو تا را خودشون رو اول مرتب کنیم + زمانی که این دو تای مرتب شده رو ادغام میکنیم(که در پاراگراف بالا فهمیدم از مرتبه N هست این یکی) ]فرض کنید f(N) پیچیدگی زمانی باشد الگوریتم MergeSort باشد. توضیحات بالا ما را به این نتیجه میرساند :معادله 1که p(N) یک تابع خطیست که بیانگر زمان مصرف شده برای شکستن آرایه اصلی به دو آرایه و ادغام کردن آن دو آرایه زمانی که مرتب شده اند هست.[توضیح مترجم : اینجا شاید یکم سخت بنظر برسه ولی خیلی پیچیده نیست. تابع f بیانگر زمان کلی مصرف شده توسط الگوریتم بر حسب سایز آرایه ای که میخوایم مرتب کنیم هست. حالا دقیقا همون توضیحات بالا آورده شده. یک f(N/2) داریم که بیانگر زمان مصرف شده برای sort کردن یکی از دو آرایه ای هست که که اون اول با شکستن آرایه N عضوی ساختیم. دوباره یک f(N/2) دیگه هم داریم که عین قبلی برای اون یکی آرایه شکسته شده هست. یدونه p(N) هم داریم که نشون دهنده زمان مصرفی برای این هست که 1: آرایه اصلی رو به دو تا آرایه N/2 عضوی بشکونیم. 2: بعد از اینکه آرایه های N/2 عضوی رو sort کردیم ، اینا رو با هم ادغام کنیم. چون نتیجه گرفتیم که هر دو تای این عمل ها از مرتبه N هستن پس قطعا جمعشون هم مرتبه N هست و در نهایت p باید خطی باشه]دقت کنید این به تعبیر متداول یک معادله نیست. مانند مثال های بخش اول این مقاله علامت تساوی به معنی "از نظر asymptotic analysis برابر است با ..." است. معمولا توابع بسیاری هستند که در تساوی بالا صدق می کنند اما معمولا تمام آنها از نظر مرتبه رشد یکسان هستند- که این دقیقا همان چیزی هست که ما به دنبال آن هستیم. یا در حالت کلی تر میخواهیم یک مرز بالایی نزدیک برای تمامی جواب هایی که در معادله بالا صدق می کنند بیابیم.در بخش های انتهایی این مقاله روش های متفاوتی را برای یافتن این "معادلات" بررسی میکنیم. قبل از آن نیاز داریم که کمی راجع به لگاریتم صحبت کنیم.[توضیح مترجم : توابع لگاریتمی جز توابع نسبتا ساده ریاضی با تعاریف و قوانین سر راست هستند که در نظام آموزشی 6-3-3 ایران در کتاب های درسی پایه یازدهم آموخته می شوند. برای بررسی بیشتر میتوانید به این کتاب ها مراجع کنید.]نکاتی راجع به لگاریتمتا الان احتمالا یکی از این سوالات را از خودتان پرسیده اید : هنگامی که نویسنده میگوید پیچیدگی یک تابع از مرتبه مثلا O(N*Log(N)) است ، پایه لگاریتم چیست ؟ آیا در بعضی موارد بیان کردن پیچیدگی با لگاریتم پایه 2 بهتر نیست؟پاسخ: پایه لگاریتم اصلا مهم نیست. تمام لگاریتم ها از نظر مرتبه رشد یکسان هستند. این به علت قانون زیر در لگاریتم هاست:دقت کنید که اگر a و b را مثل بالا پایه های لگاریتم در نظر بگیریم لگاریتم a در پایه b (مخرج کسر) یک ثابت است.در نتیجه لگاریتم N در پایه a همواره ضریبی از لگاریتم N در پایه b خواهد بود.برای دادن توضیحات بهتر و نوشتن عبارات ساده تر ما همواره از عبارت log(n) درون علامت big-Oh استفاده می کنیم ، چه بسا لگاریتم با پایه های مختلفی برای محاسبه مرز های تابع استفاده شده باشد.در ضمن متاسفانه معنی log(N) در کشور های مختلف یکسان نیست و از کشور به کشور میتواند فرق کند.برای جلوگیری از ایجاد ابهام منظور من از log(N) در مبنای 10 است و منظورم از lg(N) لگاریتم N در مبنای 2 است و در بقیه موارد پایه ذکر می شود.حالا چند تکنیک لگاریتمی به شما نشان میدهیم که در ادامه از آنها استفاده می کنیم.با فرض اینکه a و b ثابت هایی بزرگتر از 1 باشند :با دانستن قاعده بالا میتوانیم نتیجه زیر را بگیریم :روش های حل معادلات بازگشتی:روش اول :جانشینیاین روش را میتوانیم در یک جمله خلاصه کنیم: یک حد بالایی برای f حدس میزنیم و سپس حدس را با استقرا ثابت می کنیم:برای مثال ثابت می کنیم که اگر f در معادله 1 صدق کند آنگاه f(N)=o(Nlog(N)).از معادله 1 میدانیم برای بعضی از مقادیر c :حالا ثابت می کنیم که اگر d را به اندازه کافی بزرگ انتخاب کنیم آنگاه برای تقریبا همه N ها داریم : f(N) <= d(n*lg(N)). اثبات را از حکم مسئله شروع می کنیم:به عبارت دیگر حکم استقرا تا وقتی که d>c باشد برقرار خواهد بود. از آنجایی که d و c ثابت های دلخواه هستند ما میتوانیم این فرض را درست در نظر بگیریم.تنها کاری که الان باید انجام دهیم ثابت کردن معادله برای یک مقدار اولیه N است. هنگامی که بخواهیم اینکار را بصورت ریاضیاتی/استقرایی انجام دهیم کار بسیار دشوار می شود اما ایده کلی این است که هر گاه d به اندازه کافی بزرگ نبود میتواند بزرگتر انتخاب شود تا مقادیر اولیه N را پوشش دهد.روش دوم : درخت بازگشتبرای یک مبتدی روش قبلی خیلی کارآمد واقع نخواهد شد.برای اینکه از روش قبلی استفاده کنیم باید یک حدس نسبتا خوب بزنیم-و برای اینکه حدس خوب بزنیم نیاز به بینش/تجربه داریم. سوال این است که چگونه این بینش را به دست آوریم؟ اجازه دهید یک نگاه نزدیک تر به آنچه که وقتی میخواهیم الگوریتم های بازگشتی را آنالیز کنیم اتفاق می افتد داشته باشیم.(در حقیقت اتفاقاتی که هنگامی که یک برنامه بازگشتی را اجاره میکنیم رخ میدهد)ما میتوانیم اجرای یک برنامه بازگشتی با یک ورودی مشخص را به وسیله یک درخت شاخه شاخه نشان دهیم.هر سر شاخه نشان دهنده یک نمونه از سوالی است که برنامه قصد حل کردنش را دارد.یک راس دلخواه برای درخت در نظر بگیرید.اگر حل کردن سوال در آن راس نیازمند فراخوان کردن توابع بازگشتی است این راس خود شامل شاخه هایی هست که وظیفه حل کردن سوال برای بخش های کوچکتر را بصورت بازگشتی دارند و به همین ترتیب ...بالاترین راس (راس خود درخت) ورودی اصلی ما است و برگ ها ( راس های پایین پایین) نشان دهنده مسائل ساده و کوچک هستند که میتوانیم آن ها را حل کنیم.[توضیح مترجم: این بخش نوشته شاید کمی گنگ بنظر برسد در مثال های بعدی احتمالا منظور را متوجه می شوید]مثال 4: درخت بازگشتی برای الگوریتم MergeSort روی یک آرایه 5عنصری به این شکل است:در اینجا درسته که آرایه به دو بخش دقیقا مساوی تقسیم نشده ( چون ورودی فرد هست ) ولی خب در اصلیت کار تفاوت فاحشی به وجود نمیاد.درخت بازگشتی برای معادله بازگشتی متناظر با الگوریتم به شکل زیر است. اینبار عدد نوشته شده در هر خانه تعداد قدم های الگوریتم هست.[منظور از قدم در اینجا اعمال ساده از O(1) است مثل جمع، ضرب،دسترسی به خواندن و نوشتن در مموری و ...]توجه داشته باشید که با روشی تقریبا مشابه میتوان درخت بازگشت را برای هر الگوریتم بازگشتی دلخواه رسم کرد. دوست قدیمی مان یعنی معادله (1) را به خاطر آورید. در اینجا میدانیم که ثابتی مثل C وجود دارد که تعداد عملیات های الگوریتم در هر راس از c در مقدار N در آن زمان بیشتر نمی شود. بنابراین درخت مثال زیر در حقیقت بدترین سناریو است:مثال 5: درخت بدترین حالت برای معادله بازگشتی (1) :حالا روش معمول در ترکیبیات این است که عناصر با ترتیبی غیر از ترتیبی که در آن قرار دارند جمع بزنیم. در مثال یک تراز دلخواه از درخت را در نظر بگیرید(مجموعه ای از رئوس که از راس اصلی به یک فاصله قرار دارند/رئوسی که در یک طبقه هستند). واضح است که مجموع رئوس این تراز/طبقه همیشه C*N میشود.حالا سوال دوم:چه تعداد طبقه وجود دارد؟(چون جمع رئوس در هر طبقه برابر است و مساوی CN است پس با ضرب CN در تعداد طبقات جمع کل رئوس معلوم می شود). تعداد طبقات در درخت همیشه متناسب با کیس های بدیهی الگوریتم هست.[توضیح مترجم:کیس های بدیهی کیس هایی هستند که بازگشت در آنها متوقف می شود و الگوریتم میتواند بدون بازگشت خروجی بدهد. در مرج سورت مثلا کیس بدیهی ورودی با یک عنصر است که الگوریتم صرفا همان عنصر را بر می گرداند و نیازی به بازگشت ندارند]میدانیم که اندازه مسئله در هر طبقه نصف می شود. بنابراین بعد از lg(n) [تکرار میکنم در مقاله برای لگاریتم در پایه دو از lg استفاده می شود] به کیس بدیهی T(1) میرسیم که از مرتبه 1 است. در نتیجه تعداد طبقات از مرتبه تتا log(N) است. [ اشاره شد که پایه لگاریتم در Asymptotic Analysis اهمیت ندارد. ]با در نظر گرفتن دو جوابی که یافتیم یعنی هزینه در هر طبقه و تعداد طبقات به این نتیجه میرسیم که کار کل انجام شده از مرتبه N*log(N) است.مثال 6: بیاید روش جدیدمان یعنی "درخت بازگشتی" را برای حل معادله بازگشتی زیر به کار ببریم:درخت بازگشتی معادله فوق به شکل زیر خواهد بود:بیاید جمع چند طبقه اول را محاسبه کنیم:واضح است که هر چه در درخت به طبقات پایین تر می رویم مجموع کار انجام شده طبقه ای که در آن قرار داریم کاهش می یابد.سوال این است: سرعت کاهش آن چقدر است؟ هنگامی که یک طبقه پایین می رویم تعداد مسائلی که باید در طبقه جدید حل شود سه برابر می شود ولی در عوض اندازه آن مسائل تقسیم بر دو میشود، در نتیجه زمان حل آن مسئله تقسیم بر 8 می شود. [ چون در معادله زمان صرف شده برای بخش غیر بازگشتی از مرتبطه N^3 است ] در نتیجه زمان کل صرف شده برای طبقه پایین 3/8 طبقه بالاتر از خودش است.با تفاسیر بالا زمان صرف شده در هر طبقه از درخت بالا یک دنباله هندسی تشکیل می دهد.[ دنباله های حسابی/هندسی در ریاضیات سال دهم دبیرستان مورد بحث واقع می شوند. دنباله هندسی دنباله ای است که هر جمله آن با ضرب جمله قبلی در عددی ثابت(قدر نسبت) به دست می آید. ]بیاید تصور کنیم که دنباله بی نهایت جمله دارد ، آنگاه مجموع جملات آن می شود:[ مجموع جملات دنباله هندسی با بینهایت جمله(مثبت) که قدر نسبت q<1 دارند هنگامی که دنباله با جمله a شروع شود در بینهایت به a/(1-q) میل خواهد کرد.]میبینیم که در بدترین حالت یعنی بینهایت طبقه هم مجموع کار انجام شده از مرتبه تتا N^3 است.نکته مهم از این مثال: اگر کار انجام شده در طبقات یک درخت بازگشتی دنباله هندسی نزولی تشکیل دهند کار کل انجام شده در درخت تقریبا هم مرتبه کار انجام شده در راس های پایین ترین طبقه است.از این نکته میتوانیم یک به یک حقیقت جالب راجع به الگوریتم(فرضی) پشت این معادله پی ببریم: بازگشت زدن به الگوریتم در اینجا زمان زیادی مصرف نکرده است. بیشترین زمان در هر طبقه بجای بازگشت زدن به تابع ، محاسبه ورودی ها و پردازش خروجی تابع بر اساس بازگشت بوده.(در نتیجه اگر بخواهیم الگوریتم را بهینه تر کنیم باید این بخش را تغییر دهیم.)مثال 7: اکنون بیاید با روش "درخت بازگشتی" معادله زیر را حل کنیم:درخت بازگشتی چیزی شبیه تصویر زیر است:مانند قبل کار انجام شده در چند طبقه اول را حساب می کنیم:اینبار قضیه بر عکس است. هر چه به طبقات پایین تر می رویم انگار کار انجام شده در آن طبقه بیشتر می شود. هر طبقه که پایین می رویم تعداد مسائل برای حل شدن 5 برابر می شود ولی اندازه آنها 3 برابر که چون کار انجام شده مستقل از بازگشت برای هر مسئله از مرتبه Theta(N) است پس کار کل انجام شده در طبقه 5/3 برابر می شود.مثل قبل میخواهیم کل کار در همه طبقات را محاسبه کنیم. اینبار مسئله خیلی آسان نیست زیرا اکثر کار انجام شده در طبقات پایینی اتفاق می افتد. باید تعداد طبقات را بدانیم.در پایین ترین طبقه مسائل اندازه 1 دارند. میتوان مشاهده کرد که طبق الگوی درخت در طبقه k ام سایز مسائل N/3^k است. با قرار دادن این عبارت برابر 1 شماره طبق آخر بر حسب N برابر با k = log3(N) به دست می آید. یعنی تعداد طبقات لگاریتم N در پایه 3 است. دقت کنید در اینجا ما پایه لگاریتم را گفتیم زیرا برخلاف نتیجه کلی که در نماد می آید برای جمع کل کار در طبقه ها پایه لگاریتم اهمیت زیادی دارد.درخت ما log3(N) طبقه دارد. با قرار دادن مشخصات در رابطه مجموع جملات دنباله بازگشتی با داشتن تعداد جملات که همان تعداد طبقات است و دانستن قدرنسبت یعنی 5/3، کل کار انجام شده در درخت برابر مضربی از N به توانlog3(5) است.دوباره قصد داریم که کار انجام شده در هر طبقه را جمع بزنیم تا به کل کار الگوریتم برسیم. دوباره با رشد هندسی سر و کار داریم. اینبار بجای اینکه دقیق مجموع را حساب کنیم ، برعکسش را انجام میدهیم. اکنون یک دنباله هندسی نزولی داریم و در وضیعتی مشابه مثال قبلی هستیم. با استدلال مثل دفعه قبل به این نتیجه خواهیم رسید که جمع همه از نظر بزرگی رشد (یعنی بدون حساب ضرایب و جملات با رشد کوچک) برابر بزرگترین عنصر دنباله است.قضیه اساسی[ادامه مقاله در Top Coder مربوط به قضیه اساسی محاسبه مرتبه بزرگی است. چون این قضیه جای صحبت بیشتر و بررسی پیشرفته تر دارد سعی میکنم بعدا آنرا جداگانه و با راهنمای بهتر و کامل تر منتشر کنم.]

معرفی تازه ها در لاراول 5.5

دانا میرافضل — Tue, 12 Sep 2017 16:50:47 +0430

تازه ها در نسخه جدید لاراولفریم ورک فوق العاده ای هست . نه ؟ لاراول رو میگم ... احتمالا خودتونم حدس زدید ! در این نوشته میخوام امکانات جدید در لاراول 5.5 رو به شما معرفی کنم . یه نگاه ساده به این نوشته میتونه فرایند توسعه شما رو در پروژه های بعدی آسون تر و باحال تر کنه .قبل از هرچیزی بهتره پی اچ پی رو به نسخه هفت ارتقا بدید .ورژن جدید لاراول تنها و تنها با PHP 7 سازگار هست . پس بهتره قبل از هرچیزی یه نگاه به مشخصات پی اچ پی خودتون بندازید . دیگه کارتون قرار نیست با 5.6 و اینا راه بیوفته ... اگر ورژنش زیر 7 هست حتما PHP 7 رو نصب کنید . مایگریشن هارو تازه کنیددر ورژن های قبل لاراول دستوری داشتیم تحت عنوانphp artisan migrate:refreshبطور کلی این دستور میاد همه جدول هارو حذف میکنه . بعد چی ؟ خب دوباره دستور مایگریت رو اجرا میکنه . در نتیجه همه رکورد ها و جدول ها حذف میکنه و با یک دیتابیس تازه روبرو میشیم .در لاراول 5.5 هم دستور جدیدی داریم :php artisan migrate:freshاین دستور هم کار بالارو انجام میده . پس تفاوتشون چی هست ؟ خب چیزی که هست Refresh یکی یکی متد Down رو در مایگریشن های انجام شده اجرا میکنه و در نتیجه جدول ها پاک میشن . اما اگر مشکلی در خود مایگریشن وجود داشته باشه یا Sync مایگریت های انجام شده یا ناقص انجام شده با جدول بهم بخوره خیلی ساده داغون میشید ( البته درست کردنش کار سختی نیست ولی در طول پروژه حوصله میخواد )دستور Fresh اما کل جدول هارو Force Drop میکنه . یعنی براش مهم نیست متد Down شما چیه یا کدوم مایگریشن ها انجام شدن یا نه . کار این دستور شبیه این هست که بیاید کل جدول هارو از یه کنترل پنل مثل phpMyAdmin یا Navicat یا هر جایی پاک کنید و دوباره PHP Artisan Migrate رو اجرا کنید .هوپس برگشتهدر ورژن های قدیمی تر لاراول برای مدیریت خطا ها از پکیجی تحت عنوان Whoops استفاده میشد . خب با وجود اینکه در نسخه های اخیر این پکیج استفاده نمیشد ولی هوپس برگشته . در نگاه کلی این اینترفیسی هست که وقتی یه مشکلی در اپلیکیشن تون رخ میده باش مواجه میشد ( البته اگر خودتون هندل نکنیدش )مدیریت خطاهای جدید در لاراولتعریف دستورات شرطی در بلیددر ورژن جدید لاراول شما میتونید دستورات شرطی اختصاصی خودتون رو به سادگی با Blade::if تعریف کنید . مثلا به سادگی میتونید بجای اینکه هر بار شرط های پرکاربرد در اپ خودتون رو با @if استفاده کنید بسادگی دستورات شرطی بسازید . همین و بس !دستورات اختصاصی در اعتبارسنجی فرمبا دستور Artisan make:rule میتونید بسادگی دستورات اختصاصی خودتون برای ولیدیشن یا اعتبارسنجی ها تعریف کنید . اینکار خیلی ساده هست . دستورات ولیدیشن شما در دایرکتوری App/Rule بصورت کلاس ذخیره میشن . در هر کدوم از این کلاس ها متدی به نام handle وجود داره شما در این متد میتونید مقدار های مختلفی رو دریافت کنید و ولیدیشن رو انجام بدید . بنظرم حتما یه بار تستش کنید .کنترل فرانت اند در دست شمالاراول بصورت پیشفرض از یسری Scaffolding مثل بوتسترپ و ویو پشتیبانی میکنه . اما تیلور آتول ( سازنده لاراول ) درک میکنه که همه ما عاشق اینا نیستیم . حتی شاید به اپلیکیشنی نیاز داشته باشید که فقط API داره . خب در این حالت Preset های فرانت اند هیچ کاربردی ندارن . در لاراول 5.5 شما میتونید با دستور artisan preset تعین کنید که میخواید این Asset های فرانت اند در پروژه باشن یا نه . حتی میتونید بین Vue.JS ، ری اکت و بوتسترپ ( البته ورژن 3 ) سوییچ کنید .کشف خودکار پکیج هادر لاراول 5.5 لازم نیست بعد از نصب پکیج بیوفتید دنبال اد کردن فساد ها و سرویس پروایدر ها ، لاراول خودش این کار رو برای شما انجام میده . متد های کمکی جدید در کلاس روتدر ورژن جدید لاراول شما با دو متد Route::redirect و Route::view سر و کار دارید . ریدایرکت کارش اینه که به سادگی روت رو بدون Closure یا کنترلر ریدارکت کنید . متد ویو هم کارش به صورت ساده اینه که یک ویو رو با فراخوانی یک روت اجرا کنه . نیازی به پس کردن تابع ناشناس یا متد خاصی از کنترلر در پارامتر دوم نیست .این ها مهمترین تغییرات در لاراول 5.5 هست . اما اگر دوست دارید بیشتر بدونید من دوره ای تحت عنوان تازه ها در لاراول 5.5 در پارس کست استارت زدم . اگر دوست دارید که با این فریم ورک بیشتر آشنا بشید یا با یادگیری بصورت ویدیویی بیشتر حال میکنید میتونید یه سری به دوره تازه ها در لاراول بزنید .

تی دی دی چیست و چرا بش نیاز داریم ؟

دانا میرافضل — Mon, 14 Aug 2017 21:04:03 +0430

برنامه نویسی با محوریت تستخب چیزی درباره Test Driven Development یا به اختصار TDD میدونید ؟ اگر نمیدونید توصیه میکنم . چند دقیقه برای خوندن این نوشته وقت بزارید فکر کنم همه چی دستتون بیاد .خب بصورت کلی برای آشنایی با خیلی از مفاهیمی که اسمی شامل حروف مختلف دارن مثل همین TDD یا MVC یا BDD و ... بهترین راه اینه که بیاید بخش بخش اون رو معنی کنید . تست یا آزمایش کردن رو فکر کنم همتون بدونید به چه معناست . تست در فرایند نرم افزار هم وجود داره . خب آدمایی هستن که فکر میکنن با ورود به پنل کاربری وبلاگ ساده ای که نوشتن و ارسال یک پست وقتی پیام موفقیت آمیزی رو که طراحی کرده بودن میگیرن همه چیز به خوبی اجرا شده و وقتشه برن که قله های توسعه نرم افزار رو فتح کنن ! خب تستینگ قطعا به اون معنا نیست . بد نیست که از چیزی که نوشتید استفاده کنید و لذت ببرید و به خودتون افتخار کنید ولی این روش جالبی برای تست اپلیکیشن های بزرگ و متوسط نیست . راه حل درست چیه ؟ خب باید اپ رو با استاندارد ها و ابزار هایی که مخصوص اینکار طراحی شدن تست کنید . میپرسید چطور ؟ خب ابزار های مختلفی وجود داره که شما به عنوان توسعه دهنده اگر کار تست رو هم خودتون انجام میدید باید یکی از اونهارو انتخاب کنید . همین !به عنوان یک نیمه توسعه دهنده پی اچ پی من از دو ابزار PHP Unit و PHP Sepec استفاده میکنم . اگر تا حالا تجربه کار با PHP رو داشتید احتمالا حداقل اسم یکیشون به گوشتون خورده . خب تستینگ جذاب هست ولی وقتی جذاب تر میشه که متوجه بشید میشه با تست کردن اپ یک فرایند کامل برای توسعه طراحی کرد و طبق اون جلو رفت ! TDD یکی از همین روش ها و فرایند های توسعه هست که به چهار مرحله کلی تقسیم میشه :1.نوشتن تست هاخب میخواید شروع کنید ؟ چطوره یه تست بنویسید . نه تنها فعلا لازم نیست که تستتون موفق باشه بلکه باید یک تست ناموفق رو بنویسید ! خب هدفتون چیه ؟ شما در این مرحله مشخص میکنید که چه هدفی رو دنبال میکنید و این هدف طی چه مراحلی به دست میاد . یجورایی الگوریتم رو در ذهنتون ایجاد میکنید . برای مثال شما یک تست مینوسید برای اینکه مطمئن بشید مثلا کاربری که در سیستم شما لاگین نشده حق ارسال پاسخ به کاربران دیگه رو نداره ! خب مراحل این تست چی میتونه باشه ؟ به عنوان یک کاربر احراز هویت نشده وارد اپ شوبا ارسال یک درخواست HTTP به یک روت خاص تلاش کن که یک پاسخ برای یک کامنتی که قبلا منتشر شده ثبت کنی .منتظر یک خطا از طرف اپلیکیشن باش ( در اینجا باید انتظار خطا داشت چون در حقیقت نمیخوایم اپ ما اجازه بده کاربری که لاگین نشده بیاد چیزی بنویسه پس بش خطا میدیم و در تست هم میخوایم مطمئن بشیم که وقتی کاربر تلاش میکنه اینکار رو انجام بده یک خطای مشخص از اپلیکیشن ما میگیره ! )خب این هم از مراحل اولیه . ولی اگر دقت کنید گفتم این تست قطعا نباید با موفقیت روبرو بشه . چرا ؟؟؟ خب چون هنوز هیچ کدی ننوشتیم که این منطق رو در اپ ما ایجاد کنه . پس میریم سراغ مرحله دوم !2.بنویسیدخب الان وقتشه که انتظاراتی رو که توی تست از اپتون برآورد شده رو جواب بدید . کافیه با نوشتن کد بیاید و هر چیزی که توی تستتون بش اشاره کردید رو پیاده کنید . اگر تست جالبی طراحی کرده باشید احتمالا الان کدنویسی و الگوریتم انجام اون کار براتون خیلی واضح تر شده . کافیه ادیتورتون رو باز کنید و دوباره برید سراغ کدنویسی3.تست کنیدخب الان که کدتون رو نوشتید بهتره یه شات بش بدید ، نه !؟ خب پس دوباره تست هاتون رو اجرا میکنید و این دفعه باید منتظر پیام موفقیت باشید . الان دیگه کدتون نوشته شده و اگر به اندازه کافی دقت و حوصله به خرج داده باشید نگرانی از بابت تست نیست !ولی چیزی که هست انگار زیادی خوشبین بودیم ! اینطور نیست ؟ خب ممکنه کد شما یسری نواقصی داشته باشه که باعث بشه کار نکنه ( منظورم از نقص مشکلی هست که باعث بشه تست شما با موفقیت انجام نشه ... اینکه میتونید مصرف منابع رو بهینه تر کنید یا کد تمیز تر و خوانا تری بنویسید نقص حساب نمیشه ! اونو میزاریم برای مرحله چهارم ) خب اینجا باید به خودتون مسلط باشید و سعی کنید که با آرامش دوباره ادیتور رو باز کنید و اول یه نگاهی به کد بندازید . سعی کنید متوجه بشید که کجای کدتون خطا ایجاد کرده و اون رو اصلاح کنید . اینکارو اینقدر انجام بدید تا بلاخره پیام سبز رنگ تست موفقیت آمیز رو در خط فرمان خودتون ببینید . سعی کنید در این مرحله از اعصاب خوردی و باگ های مختلف چیزی رو نشکنید تلفات جانی هم وارد نکنید . حالا میرم سراغ بخش نهایی و چهارم !4.ریفکتور کنیدریفکتورینگ اصولا به هر کاری گفته میشه که در این مرحله کد قبلی که نوشتید رو بهتر کنه . اسم های جالبی برای کلاس ها انتخاب نکردید ؟ کدتون فشرده نیست ؟ مصرف منابع تون میتونست بهینه تر باشه ؟ میتونید کوئری های کمتری به دیتابیس بزنید ؟خب در این مرحله میتونید چیز هایی که فکر میکنید کدتون رو بهتر میکنه بش اضافه کنید یا اصلاحات لازم رو انجام بدید . این مرحله همیشه ضروری نیست ولی سعی کنید اعتماد به نفستون جلوی بقیه همکارا باعث نشه که فکر کنید کدی که نوشتید توسط CIA نوشته شده و اصلا قابلیت بهتر شدن رو نداره ! با انجام این چهار مرحله پشت سر هم برای هر یک از اجزای اپتون میتونید با افتخار بگید که دارید به روش TDD برنامه نویسی و توسعه رو انجام میدید . دیدید اصلا سخت نبود ؟؟ حالا اگر سوالی چیزی پیش اومده براتون چطوره از من همینجا ( در بخش کامنت های این نوشته ) بپرسید . منتظر نظرات ، سوالات و پیشنهاددتون هستم ;)