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


📣👨‍💻 @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

درخت جست و جوی دودویی(BST):
درخت جستجو دودویی یک درخت دودیی است که در آن هر گره از تمام کلید های زیر درخت چپ بزرگتر و از تمام کلید های زیر درخت راست کوچیک تر است.

📣👨‍💻 @AlgorithmDesign_DataStructuer

جواب:

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

📣👨‍💻 @AlgorithmDesign_DataStructuer

روش اصلی برای محاسبه الگوریتم های بازگشتی

📣👨‍💻 @AlgorithmDesign_DataStructuer