آشنایی با الگوریتم ها و پیچیدگی¶
امروزه کامپیوتر ها بسیار سریع هستند، اما هیچ کامپیوتری دستورات را در لحظه اجرا نمی کند. مقدار بسیار کوچکی از زمان طول می کشد که کامپیوتر یک دستور را اجرا کند. برای مثال کامپیوتر های امروز در فرکانس حدود سه گیگاهرتز کار می کنند که یعنی یک زیر دستور العمل را در زمان حدود سه دهم نانو ثانیه انجام می دهند که این یعنی هر دستور العمل در حدود چند نانو ثانیه زمان می برد.
با این حال کار نوشتن برنامه ای که ساعت ها، یا حتی سال ها زمان ببرد، اصلا کار سختی نیست. حتی ممکن است خودتان به آن برخورده باشید. مثلا در پردازش فیلم یا شبیه سازی های فیزیکی ممکن است ساعت ها کامپیوتر خود را روشن گذاشته باشید تا پاسخ را دریافت کنید.
به همین دلیل در مسابقات برنامه نویسی محدودیت زمانی برای اجرای برنامه شما وجود دارد و برنامه شما باید در زمانی حدود ۱ تا ۵ ثانیه (بسته به مساله) اجرا شود. به همین دلیل در هنگام طراحی الگوریتم ها محاسبه می کنیم که آیا راه ما با توجه به شرایط ورودی در زمان خواسته شده اجرا می شود یا خیر و اگر اجرا می شد شروع به پیاده سازی آن می کنیم.
تحلیل پیچیدگی¶
سخت است که زمان اجرای یک برنامه را به طور دقیق حساب کنیم. برای مثال دستور
a[x] += a[y];
را در نظر بگیرید. این دستور چند عمل در سی پی یو است؟ پاسخ به این سوال بسیار سخت و نیازمند شناخت دقیق کامپایلر و سی پی یو است. حتی ممکن است پاسخ این سوال بسته به نوع سی پی یو یا کامپایلر یا درجه بهینه سازی کامپایلر یا مکان قرار گیری این دستور در کد فرق کند. برای مثال خواندن y از حافظه، جمع x با a و خواندن خانه به دست آمده از حافظه یا جمع مقدار a[x] و a[y] می تواند یک یا چند دستور العمل در سی پی یو باشد.
حتی اگر می دانستیم که برنامه ما از چند دستور العمل تشکیل شده، باز برای تخمین زمان اجرای برنامه کافی نبود. برای مثال دستور باقیمانده و دستور شیفت بیتی هر دو یک دستور العمل هستند اما باقیمانده بسیار بیشتر از شیفت بیتی طول می کشد.
بنابراین از محاسبه زمان دقیق اجرای کد صرف نظر می کنیم و تنها به این اکتفا می کنیم که دستورات سی پی یو مانند خواندن از آرایه یا جمع دو عدد، مقدار ثابتی از زمان طول می کشند. به همین صورت، دقت اندازه گیری ما در حد یک ضریب پایین می آید. برای مثال این کد را در نظر بگیرید
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
swap(a[i],a[j]);
}
}
ما نمی دانیم که تابع سوپ یا عمل مقایسه یا عمل پلاس پلاس هر کدام چند واحد زمانی طول می کشند اما می دانیم که هر کدام مقدار ثابتی از زمان طول می کشند. پس می توان گفت که زمان اجرای این کد \(kn^2\) است که k یک ضریب ثابت با واحد ثانیه است. در عموم موارد مقدار k برای ما اهمیتی ندارد و از آن چشم پوشی می کنیم.
نماد ها¶
چون می توانیم از ضریب چشم پوشی کنیم، تعریف نماد های زیر خالی از لطف نیست:
- نماد \(f(n) = O(g(n))\): این نماد به این این معنی است که ضریبی مانند k وجود دارد به طوری که \(f(n) \le kg(n)\) به ازای تمامی n های بزرگ برقرار باشد. این نماد به صورت اِف اِن از او یِ جیِ اِن است خوانده می شود.
- نماد \(f(n) = \Omega (g(n))\): اگر و تنها اگر \(g(n) = O(f(n))\) بر قرار باشد برقرار است و می خوانیم اِف اِن از اُمِگا یِ جیِ اِن است
- نماد \(f(n) = \theta (g(n))\): اگر و تنها اگر \(f(n) = O(g(n))\) و \(f(n) = \Omega (g(n))\) بر قرار باشد برقرار است و می خوانیم اِف اِن از تِتا یِ جیِ اِن است
به این نماد ها می توانید به چشم علامت های کوچکتر مساوی، بزرگتر مساوی و مساوی نگاه کنید. مثال های زیر می تواند به درک بهتر این علامت ها کمک کند.
دسته بندی پیچیدگی های مهم¶
در مسائلی که ما بررسی می‌کنیم پیچیدگی هایی مرتبا تکرار می‌شوند که آن ها را در زیر بررسی می‌کنیم.
پیچیدگی خطی¶
به الگوریتمی که زمان اجرایش ضریبی از طول ورودی باشد، الگوریتم خطی می گوییم. اگر طول ورودی n باشد زمان اجرای الگوریتم .. math:: O(n) است. در حالت عادی نمی توان الگوریتمی بهتر از الگوریتم خطی پیدا کرد زیرا خود دریافت ورودی ضریبی از n طول می‌کشد و حتی اگر زمان ورودی گرفتن را در نظر نگیریم چون در زمان ثابت می توان روی تعداد ثابتی از متغیر ها و خانه های حافظه انجام داد پس برای این که تمام ورودی را روی خروجی اثر دهیم باید ضریبی از طول ورودی را صرف کنیم.
تابع لگاریتم¶
تابع لگاریتم تابعی است که در تحلیل پیچیدگی الگوریتم ها بسیار ظاهر می‌شود. این تابع به صورت معکوس تابع توان ۲ تعریف می‌شود. یعنی: \(2^{lg(n)} = n\) به سادگی می توان صحت گزاره های زیر را بررسی کرد.
پیچدگی شبه خطی¶
به الگوریتمی که زمان اجرایش از \(O(n*lg(n)^k)\) باشد که k عددی ثابت است، این الگوریتم زمان اجرای شبه خطی دارد.
پیچیدگی چندجمله ای¶
اگر زمان اجرای الگوریتم از \(O(n^k)\) باشد و k عددی ثابت باشد می گوییم زمان اجرای الگوریتم چند جمله ای است.
پیچیدگی نمایی¶
اگر زمان اجرای الگوریتم از \(O(c^n)\) باشد و c عددی ثابت باشد می گوییم زمان اجرای الگوریتم نمایی است. الگوریتم های نمایی عموما مناسب نیستند و برای n های بزرگ (مثلا ۱۰۰۰) می توانند به اندازه عمر کهکشان طول بشکند :))
این کتاب توسط مشارکت کنندگان شاززز به وجود آمده است.
این کتاب عمومی است و تحت پروانه cc-by-sa در دسترس است.
آخرین به روز رسانی در ژوئن 09, 2022.
