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

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

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

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

نتیجه را نمایش دهید.
📣👨‍💻 @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

جواب:
همان طور که مشاهده میکنید اگرi=1 باشد حلقه داخلی n/2بار تکرار می شود زیرا به همان صورت که j در حال افزایش است nهم در حال کاهش می باشد تا زمانی که در وسط به هم برسند در iهای بعدی هم به همین صورت میباشد بنابراین با مجموع گرفتن و دانستنی های ریاضی میتوان نتیجه گرفت که پیچیدگی این الگوریتم از مرتبه ی n می باشد.

تعریف پشته(Stack):
پشته یک ساختار داده خطی است که از اصل LIFO (Last-In-First-Out) پیروی می کند. پشته یک انتهای دارد، در حالی که صف دارای دو سر (جلو و عقب) است. این شامل تنها یک اشاره گر بالای اشاره گر است که به بالاترین عنصر پشته اشاره می کند. هرگاه عنصری به پشته اضافه شود، در بالای پشته اضافه می شود و عنصر را فقط از پشته می توان حذف کرد. به عبارت دیگر، پشته را می توان به عنوان ظرفی تعریف کرد که در آن جاگذاری و حذف از یک سر که به عنوان بالای پشته شناخته می شود، انجام شود.مثالی دیگه که میتوان برای پشته زد فرض کنیددر یک پارکینگ چند ماشین پشت سر هم قرار دارند زمانی که ماشین اول که وارد شده خارج شود باید اول ماشین هایی که بعد از اون وارد شدن خارج شوند تا بتواند از پارکینگ خارج شود. در واقع میتوان گفت در پشته کسی که زودتر از همه وارد شده دیرتر از همه هم خارج می شود.

📣👨‍💻 @AlgorithmDesign_DataStructuer

در اینجا همان طور که مشاهده می کنید پشت خالی میباشد سپس عدد 5 با استفاده از متد Push(پوش)وارد پشته می شود سپس عدد 6 وارد میشود و بعد با استفاده از متد Pop(پاپ) آخرین عددی که وارد پشته شده است را برداشت که عدد 6 میباشد و بعد هم عدد 5 و در اخر پشته خالی می شود.

📣👨‍💻 @AlgorithmDesign_DataStructuer

شاخص های کلیدی پیچیدگی یک الگوریتم

پیچیدگی مکانی :پیچیدگی مکانی یک الگوریتم کل فضای گرفته شده حافضه می باشید,که توسط یک الگوریتم گرفته میشود که در واقع میتوان گفت میزان حافظه ای است که با توجه به ورودی تابع گرفته می شود.
پیچیدگی زمانی : در واقع میتوان گفت بیشترین تعداد محاسبات یک الگوریتم با توجه به اندازه ورودی.

در این جا برای ما پیچیدگی مکانی برای ما زیاد مهم نیست و بیشتر تمرکز ما روی پیچیدگی زمانی میباشید تا بتوانیم یه الگوریتم بهینه بسازیم و سرعت اجرای برنامه را به حداقل ممکن برسانیم زیرا ممکنه است شما یک الگوریتم بسازید زمانی که اندازه ورودی را کم میدهید هیچ تأثیری در زمان نداشته باشد ولی در واقع ملاک ما اندازه ورودی زیاد میباشد که ممکن است الگوریتمی که ساختید بهینه نباشد و ممکن چند سال طول بکشد تا الگوریتم شما اجرا شود.

📣👨‍💻 @AlgorithmDesign_DataStructuer