پیچیدگی اجرایی و تحلیل الگوریتم

نقشه‌ی کلی مبحث

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

مفاهیم اصلی

مفهوم ۱

تعریف: پیچیدگی اجرایی تابعی است که زمان یا تعداد عملیات یک الگوریتم را برحسب اندازه‌ی ورودی، معمولاً ، توصیف می‌کند.
توضیح ساده: به‌جای اندازه‌گیری زمان روی یک دستگاه مشخص، بررسی می‌کنیم با بزرگ‌تر شدن ورودی، تعداد عملیات الگوریتم چگونه رشد می‌کند.
مثال: اگر تعداد عملیات متناسب با باشد، مرتبه‌ی اجرایی الگوریتم است.
نکته مهم: در تحلیل مجانبی، ثابت‌ها و جمله‌های کم‌اهمیت‌تر حذف می‌شوند.

مفهوم ۲

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

مفهوم ۳

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

مفهوم ۴

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

مفهوم ۵

تعریف: در حلقه‌های تودرتو، هزینه با جمع یا ضرب تعداد تکرارهای حلقه‌ها محاسبه می‌شود؛ در حلقه‌های پشت‌سرهم، هزینه‌ها با هم جمع می‌شوند.
توضیح ساده: حلقه‌های تودرتو که هرکدام بار اجرا می‌شوند معمولاً هزینه‌ای درجه‌دو دارند. در حلقه‌های مستقل و پشت‌سرهم، بخش غالب تعیین‌کننده‌ی مرتبه است.
مثال: دو حلقه‌ی تودرتوی -تکراری هزینه‌ی دارند. دو حلقه‌ی پشت‌سرهم با اندازه‌های و هزینه‌ی دارند.
نکته مهم: اگر تعداد تکرار حلقه‌ی داخلی به شمارنده‌ی حلقه‌ی بیرونی وابسته باشد، باید تعداد تکرارها را جمع کرد؛ مثلاً .

ارتباط‌ها، روندها و نمودارها

رشد مرتبه‌های رایج از آهسته به سریع

تحلیل حلقه‌ها

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

مقایسه‌ها و دسته‌بندی‌ها

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

مثال و کاربرد

صورت سؤال -> روش حل -> مراحل -> جواب -> نکته: مرتبه‌ی حلقه‌ی زیر را تعیین کنید:
```
for i = 1 to n:
    for j = 1 to i:
        s
```
روش حل: تعداد دفعات اجرای دستور داخلی را برای هر مقدار جمع می‌کنیم.
مراحل: .
جواب: .
نکته: وابستگی حد بالای حلقه‌ی داخلی به به این معناست که تعداد تکرارها را نباید فقط از روی یک اجرای ثابت محاسبه کرد.
مثال: دو حلقه‌ی پشت‌سرهم، یکی بار و دیگری بار اجرا می‌شوند.
چرا؟ تعداد کل عملیات متناسب با است.
نتیجه: پیچیدگی است؛ برای ورودی‌های نامنفی این مرتبه با هم‌ارز است.

نکات مهم و استثناها

⭐ نکات مهم

برای جمع هزینه‌ها، جمله‌ی غالب را نگه دارید؛ مثلاً .
اگر و باشد، آنگاه و .
رابطه‌ی متقارن است؛ همچنین معادل است.

⚠️ استثنا: برای حلقه‌های وابسته، تخمین حاصل‌ضرب تعداد تکرارها ممکن است نادرست باشد؛ ابتدا تعداد تکرار واقعی را به‌صورت جمع محاسبه کنید.

خلاصه‌ی یک‌دقیقه‌ای

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

مرتب‌سازی درجی

نقشه‌ی کلی مبحث

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

مفاهیم اصلی

مفهوم ۱

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

مفهوم ۲

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

مفهوم ۳

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

ارتباط‌ها، روندها و نمودارها

درج یک عنصر

عنصر بعدی را انتخاب کن → آن را با بخش مرتب‌شده مقایسه کن → عناصر بزرگ‌تر را یک خانه به راست منتقل کن → عنصر را در جای خالی قرار بده

اثبات درستی با ناوردای حلقه

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

هزینه‌ی اجرا

آرایه‌ی مرتب → جابه‌جایی اندک →
آرایه‌ی معکوس → جابه‌جایی‌های فراوان →

مقایسه‌ها و دسته‌بندی‌ها

مورد	ویژگی	کاربرد	نکته
بهترین حالت	آرایه از پیش مرتب است	ورودی مرتب یا تقریباً مرتب
بدترین حالت	آرایه به‌شکل معکوس مرتب است	تحلیل بیشترین جابه‌جایی
حالت متوسط	ترتیب ورودی دلخواه است	تحلیل عملکرد معمول
مرتب‌سازی درجی	درجا و پایدار	آرایه‌های کوچک یا تقریباً مرتب	حافظه‌ی کمکی ثابت دارد

مثال و کاربرد

صورت سؤال -> روش حل -> مراحل -> جواب -> نکته: آرایه‌ی را مرتب کنید. روش حل: هر عنصر را به نوبت در بخش مرتب‌شده‌ی سمت چپ درج کنید. مراحل: ← ← ← ← . جواب: . نکته: عنصرهای بزرگ‌تر از عنصر در حال درج به سمت راست منتقل می‌شوند.

نکات مهم و استثناها

⭐ نکات مهم

درستی الگوریتم از مرتب بودن پیشوند آرایه در آغاز هر تکرار نتیجه می‌شود.
بهترین حالت و بدترین و متوسط حالت است.
الگوریتم پایدار است و در محل مرتب می‌کند.

⚠️ استثنا: برای داده‌های بزرگ و نامرتب، رشد درجه‌دو باعث می‌شود مرتب‌سازی درجی معمولاً از الگوریتم‌هایی با مرتبه‌ی کندتر باشد.

خلاصه‌ی یک‌دقیقه‌ای

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

رابطه‌های بازگشتی

نقشه‌ی کلی مبحث

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

مفاهیم اصلی

مفهوم ۱

تعریف: رابطه‌ی بازگشتی تابعی را با استفاده از مقدارهای همان تابع برای ورودی‌های کوچک‌تر تعریف می‌کند؛ شرایط اولیه نیز برای تعیین جواب لازم‌اند.
توضیح ساده: هزینه‌ی مسئله‌ی بزرگ را از هزینه‌ی مسئله‌های کوچک‌تر و کار اضافی هر مرحله محاسبه می‌کنیم.
مثال: برای محاسبه‌ی فاکتوریل بازگشتی، تعداد ضرب‌ها را می‌توان چنین نوشت: و برای .
نکته مهم: رابطه‌ی بازگشتی بدون شرایط پایه معمولاً جواب یکتایی تعیین نمی‌کند.

مفهوم ۲

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

مفهوم ۳

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

مفهوم ۴

تعریف: قضیه‌ی اصلی برای رابطه‌های تقسیم‌و‌حل به‌شکل ، مرتبه‌ی تابع را با مقایسه‌ی و به‌دست می‌دهد.
توضیح ساده: هزینه‌ی کل سطح برگ‌ها را تقریباً نشان می‌دهد؛ پاسخ به این بستگی دارد که هزینه‌ی بیرون از فراخوانی‌ها کوچک‌تر، هم‌مرتبه یا بزرگ‌تر باشد.
مثال: ؛ چون از کم‌رشدتر است، در صورت برقرار بودن شرط منظم‌بودنِ حالت سوم، .
نکته مهم: شکل ساده‌ی قضیه سه حالت اصلی دارد و برای حالت سوم شرط منظم‌بودن لازم است.

مفهوم ۵

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

مفهوم ۶

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

ارتباط‌ها، روندها و نمودارها

چرخه‌ی حل رابطه‌ی بازگشتی

تعریف رابطه و شرایط پایه → انتخاب روش حل → بازکردن یا تحلیل زیرمسئله‌ها → محاسبه‌ی مجموع یا حل معادله → تعیین مقدار یا مرتبه‌ی نهایی

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

سطح ریشه: هزینه‌ی
سطح بعد: دو زیرمسئله با مجموع هزینه‌ی
سطح‌های بعد: هزینه‌ی کل هر سطح همچنان
تعداد سطح‌ها: تقریباً
مجموع هزینه‌ها:

قضیه‌ی اصلی

برای ، با تعریف :

اگر برای یک ، آنگاه .
اگر برای ، آنگاه .
اگر و شرط منظم‌بودن برقرار باشد، آنگاه .

مقایسه‌ها و دسته‌بندی‌ها

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

مثال و کاربرد

صورت سؤال -> روش حل -> مراحل -> جواب -> نکته: مرتبه‌ی رابطه‌ی را تعیین کنید، با فرض . روش حل: درخت بازگشت یا قضیه‌ی اصلی. مراحل: در قضیه‌ی اصلی ، و ؛ بنابراین و دو بخش هم‌مرتبه‌اند. جواب: . نکته: در روش درخت، هزینه‌ی هر سطح و تعداد سطح‌ها تقریباً است.
مثال: برج هانوی با یک دیسک یک حرکت نیاز دارد و برای دیسک، رابطه‌ی برقرار است.
چرا؟ ابتدا دیسک را جابه‌جا می‌کنیم، دیسک بزرگ را حرکت می‌دهیم و سپس دیسک را دوباره منتقل می‌کنیم.
نتیجه: با شرط ، تعداد حرکت‌ها است.
مثال: در مدل خرگوش‌ها، تعداد جفت‌ها از رابطه‌ی فیبوناچی پیروی می‌کند: ، و برای .

نکات مهم و استثناها

⭐ نکات مهم

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

⚠️ استثنا: قضیه‌ی اصلی را نمی‌توان بدون بررسی شرایطش به هر رابطه‌ی بازگشتی اعمال کرد؛ به‌ویژه در حالت هزینه‌ی غالب، شرط منظم‌بودن باید برقرار باشد.

خلاصه‌ی یک‌دقیقه‌ای

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

طراحی الگوریتم: مرتبه اجرایی و رابطه‌های بازگشتی