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

الگوریتم جمع دو عدد:

دو عدد ورودی بگیرید

اعداد را با استفاده از عملگر + اضافه کنید

نتیجه را نمایش دهید.
📣👨‍💻 @AlgorithmDesign_DataStructuer

خب بریم ببینیم چه عواملی در اجرای یک برنامه روی یک کامپیوتر مؤثرند:
1-سرعت پردازنده ی کامپیوتر
2-نوع کامپیایلر یا زبان برنامه نویسی استفاده شده
3-اندازه داده ورودی سوال
4-ترکیب یا ساختار داده های ورودی
5-پیچیدگی الگوریتم استفاده شده در برنامه
6-عوامل دیگه که تأثیر خطی روی اجرا برنامه میزارن
از این عواملی گفته شد مثل سرعت پردازنده , نوع کامپایلر استفاد شده ضریب ثابتی هستند که در اجرای برنامه مؤثرند.یعنی اگر ما بیایم پرازنده کامیپوتر را دو برابر سریع کنیم انتظار داریم که در بهترین حالت زمان اجرای یک برنامه نصف شود.
از عوامل ذکر شده پیچیدگی الگوریتم که در برنامه استفاده میشود یکی از ویژگی های مهم است.پیچیدگی یک الگوریتم یک مفهوم انتزاعی و مستقل از زبان برنامه نویسی و سخت افزار میباشد که معمولا آن را به صورت تابع نمایش میدهند.

📣👨‍💻 @AlgorithmDesign_DataStructuer

عوامل مهم برای ساختن یک الگوریتم کارا :
1-Input 2-Output 3-Definitenss 4-Correctness 5-Finiteness 6-Effectiveness 7-Generality
۱-ورودی
۲-خروجی
۳-با پایان بودن الگوریتم : هر دستورالعلی که به الگوریتم میدیم یک جواب بیشتر نداشته باشه.
۴-درست باشه : هر نمونه میدهیم جواب متناظر با اون نمونه رو تولید کنه.
۵-متناهی بودن : یعنی الگوریتم من باید یه جایی متوقف بشه و بی پایان نباشه.
۶-کارا بودن الگوریتم : برای حل مسئله بیش از حد زمان مصرف نشه تا جایی که ممکنه با خداقل کردن کد اون الگوریتم که که برای حل مسئله میخواهیم انجام بشه.
۷-قابلیت طعمیم داشته باشه.

📣👨‍💻 @AlgorithmDesign_DataStructuer

فرمول زمان اجرای یک قطعه کد:

مجموعه تعداد بار اجرای هر خط * زمان اجرای هر خط

نکته:زمان اجرای هر خط (ضریب ثابت) در مرتبه تأثیری ندارد و بیان نمیشود.

📣👨‍💻 @AlgorithmDesign_DataStructuer

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

هر برنامه بازگشتی، مراحلی اصلی ای را دنبال می کند که به شرح زیر است:

1-الگوریتم را راه اندازی کنید. برنامه های بازگشتی اغلب برای شروع، به یک مقدار اولیه نیاز دارند. این کار یا با استفاده از پارامتری که به تابع ارسال می‌شود یا توسط یک تابع دیگر که غیر بازگشتی است اما مقادیر اولیه را برای محاسبه بازگشتی در اختیار تابع بازگشتی قرار می دهد، انجام می‌شود.
2-بررسی کنید که آیا مقدار(های) فعلی که در حال پردازش آن هستید با base case (حالت پایه) مطابقت دارد یا خیر. اگر چنین است، مقدار را پردازش کرده و برگردانید.
3-پاسخ را در قالب یک زیرمسئله یا مسئله ی کوچکتر یا ساده تر تعریف کنید.
4-الگوریتم را روی آن مسئله ی کوچکتر یا ساده تر اجرا کنید.
5-نتیجه را با همان فرمولی که در نیازمندی تابع آمده است، ترکیب کنید.
6-نتیجه را برگردانید.

📣👨‍💻 @AlgorithmDesign_DataStructuer

مثالی مبنی بر الگوریتم بازگشتی :
زمانی که شما میخاید فاکوریتل یک عدد صحیح رو حساب کنید میایید خب میگید من باید از عدد یک تا اون عدد رو ضرب کنم تا بتونم فاکتوریل اون عدد رو به دست بیارم که میتونید الگوریتم زیر رو فاکتوریل یک عدد بدست اوردیم :
// factorial number 4
int tum = 1;
for (int i = 1 ; i <= 4 ;i++){
tum = tum * i;
}
cout << tum ;
// 24

ولی ما میتونم با یک الگوریتم ساده تری به سوال نگاه کنیم اونم اینکه در این سوال اگر دقت کنید هر برا عدد هی ضبدر عدد بعدی میشه تا زمانی که به اون عدد فاکتوریل برسه پس ما میتونیم بگیم که از اون عدد هی بیام ضرب کنیم به عدد های کمتر از اون عدد تا زمانیی که به صفر میرسم این طوری ما تونستم الگوریتتمون رو به دو زیر مسئله تبدیل کنیم به یه الگوریتم ساده تر و کوتاه تر برسیم که در زیر الگوریتم اون رو پیاده سازی کرده ایم :

int factorial(int n)
{
if(n == 1)
{
return 1;
}
else
{
return n * factorial(n ‑ 1);
}
}

📣👨‍💻 @AlgorithmDesign_DataStructue

استقرای ریاضی
استقرای ریاضی یکی از مفاهیم مهم در منتطق ریاضی است که از ان در طراحی راه حل بازگشتی مسئله ها , تحلیل و شمارش حالات و نیز درستی الگوریتم ها و بسیاری از موارد دیگر استفاده می شود. مفاهیم اولیه استقرا ساده است ,اما استفده از آن در اثبات برخی از مسئله ها پیچدگی هایی دارد که ممکن است به ابتکار,ذکاوت و نیز تجربه نیازمند باشد.


📣👨‍💻 @AlgorithmDesign_DataStructue

پیچیدگی الگوریتم ها
در تحیلیل یک الگوریتم ,بهترین زمان اجرای ان اهمیت چندانی ندارد,چرا که این حالت معمولا زمانی برای ورودی با تعداد کم و در شرایط خاص اتفاق می افتد , و زمان اجزا هم اغلب آن قدر کوتاه هست که مهم نیست از چه الگوریتمی استفاده شود.
اما لازم است که ما الگوریتم ها را در بدترین حالت و در صورت امکان در حالت میانگین تحلیل و بر این اساس , الگوریتم مناسب را انتخاب کنیم . اما رفتار یک الگوریتم یا پیچیدگی آن در بهترین و بدترین حالات مختلف باشد,ممکن است پیچیدگی الگوریتم در حالت میانگین بهتر از پیچیدگی آن در بدترین حالت باشد , و این اطلاعی مهم در مورد آن الگوریتم است.در چنین وضعیتی اغلب بدترین حالت به ندرت اتفاق می افتد و پیچیدگی حالت میانگین الگوریتم , همان رفتار مورد نظر است .
برای مثال , زمان اجرای الگوریتم «مرتب سازی سریع» در بدترین حالت با n^2 و در حالت میانگین متناسب با nLog nاست که اختلاف این دو تابع برای مقادیر بزرگ nچشم گیر است.

📣👨‍💻 @AlgorithmDesign_DataStructue