مقدمه ای برای تجزیه و تحلیل الگوریتم ها

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

داستان فیبوناچی:

لئوناردو از پیزا (با نام مستعار فیبوناچی) به بسیاری از موارد علاقه مند بود ، از جمله موضوعی که اکنون به عنوان پویایی جمعیت می شناسیم: به عنوان مثال ، جمعیت خرگوش ها در شرایط مناسب چقدر سریع گسترش می یابد؟

همانطور که در ریاضیات معمولی است (و تجزیه و تحلیل الگوریتم ها نوعی ریاضیات است) ، ما این مسئله را انتزاعی تر می کنیم تا ایده ای از ویژگی های کلی بدون از بین رفتن جزئیات را بدست آوریم:

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

سپس تعداد جفت های خرگوش را به عنوان تابعی از زمان بیان می کنیم (از زمان شروع آزمایش به عنوان چند سال اندازه گیری می شود):

• f (1) = 1 - ما با یک جفت شروع می کنیم
• F (2) = 1 - آنها برای داشتن سال اول بچه ها خیلی جوان هستند
• F (3) = 2 - در سال دوم ، آنها یک جفت کودک دارند
• f (4) = 3 - در سال سوم ، آنها یک جفت دیگر دارند
• f (5) = 5 - ما اولین مجموعه نوه ها را می گیریم

مشکل الگوریتمی که امروز به آن خواهیم پرداخت: چگونه F (n) را محاسبه کنیم؟

فرمول ها و نقطه شناور

شما احتمالاً در ریاضی 6a دیدید که f (n) = (x^n - ( 1-x)^n)/(x - ( 1-x)) که x = (1+sqrt 5)/2~1. 618 نسبت طلایی است. این راه حل اغلب به عنوان یک نمونه استاندارد از روش "تولید توابع" استفاده می شود.

بنابراین به نظر می رسد این یک الگوریتم است: محاسبه 1. 618^n - 0. 618^n. مشکل: برای دریافت پاسخ صحیح ، چقدر باید X را بدانید؟به عنوان مثال،اگر فقط از x = 1. 618 استفاده می کنید ، دریافت می کنید

• F (3) = 1. 99992 - به اندازه کافی به 2؟
• F (16) = 986. 698 - دور 987؟
• F (18) = 2583. 1 - باید 2584 باشد

یک الگوریتم بازگشتی

الگوریتم 1:

نمونه ای از نوع سؤال اساسی که در این کلاس مطالعه می کنیم این است که این الگوریتم چقدر زمان می برد؟چگونه باید زمان را اندازه بگیریم؟اندازه گیری طبیعی در چند ثانیه خواهد بود ، اما خوب است که پاسخی داشته باشیم که هر بار که اینتل با یک پردازنده سریعتر بیرون می آمد تغییر نمی کرد. ما می توانیم زمان را از نظر دستورالعمل های دستگاه اندازه گیری کنیم. سپس تقسیم بر سرعت دستگاه (در دستورالعمل/دوم) زمان واقعی مورد نظر ما را می دهد. با این حال ، حدس زدن از یک قطعه شبه کد ، تعداد دقیق دستورالعمل هایی که یک کامپایلر خاص تولید می کند ، دشوار است. برای بدست آوردن تقریبی خشن از این ، سعی می کنیم از نظر خط کد اندازه گیری کنیم.

مثل خرگوش است! به جز دو خط در هر تماس ، زمان N مبلغ زمان برای دو تماس بازگشتی کوچکتر است.

با برخی از کارها ، ما می توانیم معادله را حداقل از نظر F (n) حل کنیم: ما به بازگشت به عنوان شکل دادن یک درخت فکر می کنیم. ما یک گره ، ریشه درخت را ترسیم می کنیم ، برای اولین تماس ، هر زمان که روال خود را صدا کند ، کودک دیگری را در درخت می کشیم.

چهار گره داخلی این درخت برای فیبر (5) هر دو خط را می گیرد ، در حالی که پنج برگ یک خط طول می کشد ، بنابراین تعداد کل خطوط اجرا شده در تمام تماس های بازگشتی 13 است.

توجه داشته باشید که ، هنگامی که ما این کار را برای هرگونه تماس با FIB انجام می دهیم ، شماره Fibonacci f (i) در هر گره داخلی فقط تعداد برگهای زیر آن گره است ، بنابراین تعداد کل برگهای موجود در درخت فقط f (n) است. به یاد داشته باشید که برگها به عنوان یک خط کد ، گره های داخلی 2. برای شمارش گره های داخلی ، از واقعیت اساسی در مورد درختان باینری استفاده کنید (درختانی که در آن هر گره 2 فرزند دارد): تعداد گره های داخلی همیشه با تعداد برگهای منهای یک برابر است.(شما می توانید این را با القاء ثابت کنید: اگر یک برگ وجود داشته باشد و هیچ داخلی وجود نداشته باشد ، درست است و اگر 2 کودک را به یک برگ اضافه کنید صادق است.)

بنابراین خطوط f (n) در برگها اجرا می شوند ، و 2f (n) -2 در گره های داخلی ، برای کل 3f (n) -2. بیایید این کار را بر روی یک مثال ساده بررسی کنیم: زمان (5) = 3f (5) - 2 = 3 (5) -2 = 13.

این نوعی کند است به عنوان مثالبرای n = 45 یک میلیارد قدم طول می کشد. شاید بتوانیم سریعتر انجام دهیم؟

برنامه نویسی پویا

یک ایده: دلیل کند شدن آهسته ما این است که بارها و بارها دوباره همان زیرزمین ها را دوباره به دست می آوریم. به عنوان مثال ، درخت فوق دو محاسبات F (3) را نشان می دهد. دومین بار که به F (3) می رسیم ، تلاش خود را دوباره محاسبه می کنیم ، زیرا ما قبلاً یک بار آن را حل کرده ایم و جواب تغییر نمی کند. در عوض ، بیایید یک بار هر یک از زیرگروه ها را یک بار حل کنیم و بعداً به جای اینکه به طور مکرر دوباره آن را دوباره بسازیم ، راه حل را جستجو کنیم.

این ایده آسان منجر به برخی از الگوریتم های پیچیده می شود که بعداً در بخش برنامه نویسی پویا خواهیم دید ، اما در اینجا بسیار ساده است:

الگوریتم 2:

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

سه خط همیشه اجرا می شوند. خط اول در حلقه N-1 بار اجرا می شود (به جز N = 1) خط دوم در حلقه N-2 بار اجرا شد (به جز N = 1) بنابراین زمان (N) = N-1 + N-2 +3 = 2n (به جز زمان (1) = 4).

به عنوان نمونه برای n = 45 ، 90 مرحله طول می کشد ، تقریباً 10 میلیون برابر سریعتر از برنامه دیگر. حتی اگر این کار را اغلب انجام ندهید ، این یک تفاوت بزرگ برای توجه است ، بنابراین الگوریتم دوم بسیار بهتر از اولین است.

پیچیدگی فضا

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

باز هم ، ما چیزها را برای برنامه های بازگشتی و تکراری متفاوت تجزیه و تحلیل می کنیم. برای یک برنامه تکراری ، معمولاً فقط به دنبال اعلامیه های متغیر (و تماس های اختصاصی برای ذخیره سازی مانند MALLOC () در C) است. به عنوان مثال ، الگوریتم 2 فقط مجموعه ای از شماره های N را اعلام می کند. تجزیه و تحلیل فضای برنامه بازگشتی پیچیده تر است: فضای مورد استفاده در هر زمان ، کل فضای استفاده شده توسط تمام تماس های بازگشتی در آن زمان است. هر تماس بازگشتی در الگوریتم 1 فضای ثابت را به خود اختصاص می دهد: برخی از فضا برای متغیرهای محلی و آرگومان های عملکرد ، بلکه برخی از فضایی برای به خاطر سپردن هر تماس باید به آنجا برگردد. تماس های فعال در هر زمان ، مسیری را در درختی که قبلاً ترسیم کردیم تشکیل می دهیم ، که در آن استدلال در هر گره در مسیر یک یا دو واحد کوچکتر از استدلال در والدین آن است. طول هر مسیری می تواند حداکثر N باشد ، بنابراین فضای مورد نیاز الگوریتم بازگشتی دوباره (برخی از زمان های فاکتور ثابت) n است. ما با استفاده از نماد "O": O (N) "برخی از زمان های عامل ثابت" را خلاصه می کنیم.

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

الگوریتم 3:

در اینجا C نشان دهنده f [i] ، b f [i-1] است ، و a نمایانگر f [i-2] است. دو تکلیف اضافی پس از جمع ، این مقادیر را در آماده سازی برای تکرار بعدی تغییر می دهند. این الگوریتم از خطوط تقریباً 4N برای محاسبه f (n) استفاده می کند ، بنابراین از الگوریتم 2 کندتر است ، اما از فضای بسیار کمتری استفاده می کند.

نماد بزرگ "O"

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

مشکلی در تجزیه و تحلیل دو الگوریتم فوق: یک خط کد چیست؟اگر از Whitespace برای شکستن یک خط به دو استفاده کنم ، سرعت برنامه را تغییر نمی دهد اما تعداد خطوط اجرا شده را تغییر می دهد. و همانطور که قبلاً ذکر شد ، اگر یک کامپیوتر سریعتر بخرم ، سرعت برنامه را تغییر می دهد اما تجزیه و تحلیل را تغییر نمی دهد.

برای جلوگیری از جزئیات اضافی مانند فضای خالی و نوع کامپیوتر، از نماد "big O" استفاده می کنیم. ایده: ما قبلا زمان ها را به عنوان تابعی از n می نویسیم. نماد O بزرگ دو تابع را تقریباً یکسان در نظر می گیرد اگر یکی c برابر دیگری باشد که c ثابت باشد (چیزی که به n بستگی ندارد). بنابراین برای مثال ما 3F(n)-2 را با O(F(n)) و هر دو 2n و 4n را با O(n) جایگزین می کنیم.

ما به طور رسمی این را می گوییم

اگر مقداری c ثابت وجود داشته باشد به طوری که درست است که 4n=O(n)، اما این نیز درست است که n=O(4n). اما توجه داشته باشید که این همیشه یک رابطه متقارن نیست. n=O(F(n)) اما اینکه F(n)=O(n) درست نیست. در عمل ما معمولا فقط از نماد O برای ساده کردن فرمول ها با نادیده گرفتن عوامل ثابت و سایر جزئیات اضافی استفاده می کنیم.

منظور از نماد O چیست؟اول، با این امکان زندگی را آسان تر می کند و به ما اجازه می دهد کمتر مراقب جزئیات دقیق رفتار یک الگوریتم باشیم. اما همچنین به ما اجازه می دهد تا دو الگوریتم را به راحتی مقایسه کنیم. الگوریتم 2 و الگوریتم 3 هر دو O(n) هستند. با توجه به تعداد خطوط اجرا شده، یکی دو برابر سریعتر از دیگری است، اما این نسبت به عنوان تابعی از n تغییر نمی کند. عوامل دیگر (مانند مدت زمان لازم برای تخصیص آرایه بزرگ در الگوریتم 2) ممکن است به این معنی باشد که در زمان واقعی، الگوریتم ها به یکدیگر نزدیک تر هستند. تجزیه و تحلیل دقیق تری لازم است تا مشخص شود کدام یک از این دو مورد استفاده قرار گیرد. از سوی دیگر، ما می دانیم که 4n برای هر مقدار معقول n بسیار بهتر از 3F(n)-2 است -- اما این به ضریب 4 در کران زمانی 4n بستگی ندارد، بلکه برای7n یا 12nبرای n بزرگتر و بزرگتر، نسبت n به F(n) بسیار بزرگ می شود، به طوری که خیلی سریع هر O(n) سریعتر از هر O(F(n) خواهد بود). جایگزینی 4n با O(n) انتزاعی است که به ما امکان می دهد آن را با سایر توابع مقایسه کنیم بدون اینکه جزئیات خاصی (4) مانع ایجاد شود.

برق رسانی بازگشتی

در اینجا یک ترفند ریاضی با ماتریس ها وجود دارد:

(برای درک این موضوع لازم نیست جبر خطی زیادی را به خاطر بسپارید - فقط فرمول ضرب دو ماتریس متقارن 2x2: سپس می توانید نتیجه بالا را با استقرا ثابت کنید: فرض کنید با استقرا معادله بالا برای مقداری n درست است.، با استفاده از فرمول ضرب ماتریس، هر دو طرف را در توان دیگری از A ضرب کنید و بررسی کنید که عبارت هایی که به دست می آورید با فرمول تعیین کننده اعداد فیبوناچی یکسان هستند.)

ما می توانیم با استفاده از ضرب ماتریس از این استفاده کنیم تا الگوریتم تکراری دیگری را تعریف کنیم. اگرچه من این را در نحو C می نویسم ، ما شروع به رسیدن به شبه کد می کنیم ، زیرا C ضرب ماتریس را به روشی که من در زیر نوشته ام ساخته نشده است. الگوریتم زیر یک ماتریس M را به ماتریس هویت ("قدرت صفر" A) آغاز می کند و سپس به طور مکرر M را با A ضرب می کند تا قدرت ST (N-1) را تشکیل دهد. سپس با فرمول بالا ، گوشه بالا سمت چپ F (n) را نگه می دارد ، مقدار ما می خواهیم برگردیم.

الگوریتم 4:

این زمان O (n) (خیلی بهتر از الگوریتم 1) طول می کشد اما احتمالاً تا حدودی کندتر از الگوریتم 2 یا الگوریتم 3 است. بهتر.) مانند الگوریتم 3 ، این فقط از فضای O (1) استفاده می کند.

اما ما می توانیم سریعتر m^n را محاسبه کنیم. ایده اصلی: اگر می خواهید به عنوان مثال محاسبه کنید. 3^8 می توانید 8 3 را با هم یک بار ضرب کنید (3*3*3*3*3*3*3*3) یا می توانید به طور مکرر مربع: مربع 3^2 = 9 ، 9^2 = 3^4= 81 ، 81^2 = 3^8 = 6561. ایده مربع از ضربهای بسیار کمتری استفاده می کند ، زیرا هر یک از این نمایندگی دو برابر می شود و نه اینکه یک نفر را به آن اضافه کند. با برخی از مراقبت ها ، همان ایده برای ماتریس کار می کند و می تواند به غیر از قدرتهای دو ، به نمایندگی ها گسترش یابد.

الگوریتم 5:

اساساً تمام وقت در Matpow است ، که بازگشتی است: سعی می کند با مربع کردن قدرت (N/2) قدرت نهم A را محاسبه کند. اما اگر n عجیب باشد ، دور N/2 را دور می زند و این قدرت را در قدرت (N-1) ST به دست می آورد ، که ما با ضرب یک عامل دیگر A "رفع" می کنیم.

این یک الگوریتم بازگشتی است ، بنابراین طبق معمول ، ما یک رابطه عود را تعیین می کنیم ، فقط با نوشتن زمان صرف شده در یک تماس با Matpow (O (1)) به علاوه زمان در هر تماس بازگشتی (فقط یک تماس بازگشتی ، با استدلالn/2). بنابراین عود است

معلوم است که این مسئله به O (log n) حل می شود. برای اهداف این کلاس ، ما از Logarithms Base 2 و همه لگاریتم ها به عدد صحیح استفاده خواهیم کرد ، بنابراین Log N اساساً تعداد بیت های مورد نیاز برای نوشتن N به صورت باینری است. یک روش معادل برای تعریف آن ، کوچکترین مقدار من به گونه ای است که n<2^i. But clearly if n <2^i, n/2 <2^(i-1) and conversely, so log n satisfies the recurrence log(n) = 1 + log(n/2). The recurrence defining the time for matpow is basically the same except with O(1) instead of 1. So the solution to the recurrence is just the sum of log n copies of O(1), which is O(log n).

اگر N 1 میلیارد باشد ، log n فقط 30 خواهد بود ، و این الگوریتم بهتر از الگوریتم های 2 و 3 به همان روشی است که آنها بهتر از الگوریتم 1 هستند.

(این در واقع تا حدودی تقلب است: برای اینکه بتوانید از آن برای n برابر با یک میلیارد استفاده کنید، باید بتوانید پاسخی را بنویسید که دارای ارقام O(n) است، و باید بتوانید متغیرهایی را با این تعداد ذخیره کنید. اعداد. دستکاری چنین اعداد بزرگی بیشتر شبیه گام های O(n) در هر عملیات طول می کشد، که در اینجا ما فقط یک مرحله را در هر ضرب یا جمع صحیح می شماریم. اما حتی اگر از یک کتابخانه ویژه برای برخورد با اعداد بزرگ استفاده کنید، الگوریتم 4 خواهد بود. خیلی سریعتر از بقیه.)

در واقع می توانید فرمول اصلی 1. 618^n را با استفاده از یک ترفند مربع سازی مکرر مشابه، همچنین با زمان O(log n) به کار ببرید. بنابراین برای تشخیص اینکه کدام بهتر است، باید مراقب باشید و فقط از O-notation استفاده نکنید - برخورد با یک ماتریس عدد صحیح تا حدودی ساده تر از محاسبه ریشه های مربع ممیز شناور است تا برنده شود.

این همان مقایسه ای است که تحلیل الگوریتم ها در مورد آن است.