طراحی الگوریتم ها

🌱 جلسه اول: مقدمه‌ای بر الگوریتم‌ها و تحلیل آن‌ها
1. تعریف الگوریتم
الگوریتم (Algorithm) مجموعه‌ای از مراحل دقیق، محدود و قابل‌اجرا برای حل یک مسئله است.

به‌طور ساده: الگوریتم یعنی طرز فکر گام‌به‌گام برای رسیدن از ورودی به خروجی.

🔹 مثال:

الگوریتم مرتب‌سازی اعداد:

کوچک‌ترین عدد را پیدا کن
آن را در ابتدای لیست قرار بده
برای بقیه‌ی عناصر همین کار را تکرار کن
2. ویژگی‌های یک الگوریتم خوب
یک الگوریتم باید:

ورودی مشخص داشته باشد
خروجی مشخص تولید کند
تعداد مراحل محدود داشته باشد
در هر مرحله، دستورالعمل دقیق و واضحی داشته باشد
در زمان محدود قابل‌اجرا باشد
3. تحلیل الگوریتم‌ها (Algorithm Analysis)
تحلیل الگوریتم یعنی بررسی کارایی آن از نظر:

زمان اجرا (Time Complexity): چقدر طول می‌کشد؟
فضای مورد نیاز (Space Complexity): چقدر حافظه نیاز دارد؟
تحلیل معمولاً در دو حالت بررسی می‌شود:

حالت بدترین اجرا (Worst Case)
میانگین حالت (Average Case)
بهترین حالت (Best Case)
4. پیچیدگی زمانی (Time Complexity)
پیچیدگی زمانی یعنی رابطه‌ی بین تعداد مراحل اجرا و اندازه‌ی ورودی (n).

برای تحلیل از نمادگذاری مجانبی (Asymptotic Notation) استفاده می‌کنیم.

نمادهای مهم:

نماد توضیح
O(f(n)) حد بالای رشد — حداکثر زمان مورد نیاز
Ω(f(n)) حد پایین رشد — حداقل زمان مورد نیاز
Θ(f(n)) رشد تقریبی واقعی — زمانی که تابع محدود بالایی و پایینی دارد
🔹 مثال:

الگوریتمی که باید هر عنصر از یک آرایه‌ی n عنصری را بررسی کند، پیچیدگی زمانی آن O(n) است.

5. پیچیدگی فضایی (Space Complexity)
این معیار نشان می‌دهد الگوریتم برای اجرا به چه مقدار حافظه‌ی اضافی نیاز دارد.

مثلاً در الگوریتم جست‌وجوی دودویی، فضای مورد نیاز O(1) (ثابت) است،

در حالی‌که در مرتب‌سازی بازگشتی (مثل Merge Sort) ممکن است O(n) باشد.

6. مقایسه‌ی نرخ رشد توابع مجانبی
وقتی n بزرگ شود:

content_copy
text
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
7. هدف اصلی تحلیل الگوریتم‌ها
هدف این نیست که سریع‌ترین یا کم‌فضاترین برنامه را بنویسیم؛

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