عوامل مهم برای ساختن یک الگوریتم کارا :
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

برنامه چیست؟ همان الگوریتم است که در چارچوب قوانین یک زبان برنامه نویسی مثل cpp,javaو... نوشته میشود.

تفاوت هایی بین برنامه و الگوریتم وجود دارد از جمله :
۱-برنامه نبایستی حتما پایان پذیر باشد ولی الگوریتم پایان پذیر است.
۲-الگوریتم را میتوان به هر شکلی نوشت(شبه کد-نمودار گردشی و...) ولی برنامه باید در چار چوب یک زبان نوشته شود.

نکته : الگوریتم عبارت است از مراحل حل یک مسئله که در هر مرحله به خوبی تعریف شده باشد.

📣👨‍💻 @AlgorithmDesign_DataStructuer

نکته : در پیچیدگی زمانی یک الگوریتم اگر حلقه های forتو در تو باشند یعنی به هم وابسته نباشند در هم ضرب میشوند ولی زمانی که بصورت مجذا از هم باشند با یکدیگر جمع میشوند.


📣👨‍💻 @AlgorithmDesign_DataStructuer

همان طور که مشاهده می کنید مجموع زمان اجرای این قطعه کد 2 میباشد و ما زمانی که پیچیدگی یک الگوریتم عدد ثباتی باشد آن را از مرتبه 1 در نظر میگیریم.

📣👨‍💻 @AlgorithmDesign_DataStructuer

جواب :
در این سوال چون دو حلقه تو در تور داریم میتوان گفت که جواب n^2میباشد زیرا که مهم نیست که بازه حلقه فور ما از کجا شروع میشود.

📣👨‍💻 @AlgorithmDesign_DataStructuer

ویژگی توابع بازگشتی :
1 -از معایب توابع بازگشتی این است که در نهایت سادگی حجم زیادی را اشغال کرده و
نسبتا کند عمل می کنند و نیز در زمان پردازش cpu را درگیر می کنند.
2 -خود را فراخوانی می کنند.( تعداد دفعاتی که خود را فراخوانی می کند باید محدودباشد.بدیهی است که در غیر این صورت اجرای آن خاتمه نمی یابد.)
3 -دارای شرط خاتمه می باشد.

📣👨‍💻 @AlgorithmDesign_DataStructuer

آرایه:
آرایـه نوعی ساختمان داده است که عناصر آن هم نوع بوده و هر یک از عناصر با یک اندیس به صورت مسـتقیم قابـل دسـتیابی اسـت. آرایـه مـیتواند یک بعدی , دو بعدی و یا چند بعدی باشد.آرایه های دو بعدی را با نام ماتریس میشناسیم.

[L1 … U1 , L2 … U2 , Ln … Un]
Array [L … U]
size of Array = U-L+1
[ U1 – L1 + 1][U2 – L2 + 1][Un – Ln + 1]
Space required for the array = n × (U-L+1)

📣👨‍💻 @AlgorithmDesign_DataStructuer