Algorithm design & data structureچ

الگوریتم های تقسیم و غلبه(ِDivide and Conquer): روش تقسیم و غلبه,یک روش بالا و پایین (Top-Down)است.برای حل یک نمونه مسأله کلی ابتدا با تقسیم آن مسأله به زیر مسأله های کوچک تر(قابل حل) تلاش برای حل زیر مسأله ها شروع شده و نهایتاََ مسأله کلی نیز با حل زیر مسأله ها حل می شود .اصولا این روش به یک الگوریتم بازگشتی منجر می شود. 📣👨‍💻 @AlgorithmDesign_DataStructuer

جواب تشریحی

جست و جوی خطی در ارایه ها: تابع بالا مقدار Xرا در آرایه n عنصریA ,به روش مقایسه تک تک عناصر آرایه , جست و جو می کند .در صورت وجود اندیس آرایه (خانه حاوی X) و در صورت پیدا نکردن آن عدد1- را بر می گرداند. 📣👨‍💻 @AlgorithmDesign_DataStructuer

صف(Queue): صف یک ساختار داده انتزاعی است که تا حدودی شبیه به Stacks است. برخلاف پشته ها، یک صف در هر دو انتهای آن باز است. یک سر همیشه برای درج داده ها (enqueue) و دیگری برای حذف داده ها (dequeue) استفاده می شود. صف از First-In-First-Out پیروی می کند، به عنوان مثال، آیتم داده ای که ابتدا ذخیره شده است، ابتدا قابل دسترسی خواهد بود. یک مثال واقعی از صف می تواند یک جاده یک طرفه تک خطی باشد، جایی که وسیله نقلیه ابتدا وارد می شود، اول از آن خارج می شود. نمونه های واقعی بیشتری را می توان به عنوان صف در پنجره های بلیط و ایستگاه های اتوبوس مشاهده کرد. 📣👨‍💻 @AlgorithmDesign_DataStructuer

جواب: همان طور که مشاهده می کنید جواب گزینه 1 می باشد. الگوریتم های بازگشتی دارای مزایای زیادی هستند به همان صورت هم دارای معایبی هستند که از آن ها میتوان به اتلاف حافظه یعنی فضای زیادی را اشغال میکنند,عدم بهینه بودن آن ها یعنی ما میتوانم آن مسأله را با الگوریتم بهینه تر با هزینه کمتر حل کنیم ,همچینن میتوان به زمان اجرای بالای آن ها پرداخت که بعضی از الگوریتم های بازگشتی زمان اجرای زیادی دارند و ممکن است هزینه زیادی برای ما داشته باشد. 📣👨‍💻 @AlgorithmDesign_DataStructuer

چه طوری الگوریتم یک مسأله را پیدا کنید؟ سوالی که برای خیلی از ما پیش میاد اینکه برای حل یک سوال چه طوری باید الگوریتم آن را بدست بیاریم .راه حل برای بدست آوردن الگوریتم یک مسأله به صورت زیر میباشد: 1-ایده 2-پیاده کردن ایده 3-از درست بوده ایده اطمینان خاطر کنیم 4-پیچیدگی آن را بدست آوریم 5-بعد از انجام مراحل بالا با استفاده از یکی از زبان های برنامه نویسی آن را تست کنیم با استفاه از مراحل بالا که ذکر شد می توان الگوریتم درست کنیم البته ما به دنبال کمترین هزینه برای الگوریتم هستیم که بعدا به برخی از الگوریتم های معرفت میپردازیم. 📣👨‍💻 @AlgorithmDesign_DataStructuer

نماد O بزرگ: یک نماد ریاضی است که برای رفتار حدی یک تابع به کار می رود. این نماد که مخفف Order of growthکه به فارسی به معنای مرتبه رشد هست برای رشد الگوریتم ها به کار گرفته میشود که در وقع میتوان گفت که به معنای کران بالای رشد توابع به کار رفته در الگوریتم ها به کار می رود. تحلیل شکل: در واقع میگه از یک مقدار خاصی Xoبیشتر ,تابع gبا ضریب cمقدار بیشتری یا مساوی از تابع fمی باشد. 📣👨‍💻 @AlgorithmDesign_DataStructuer

روش اصلی برای محاسبه الگوریتم های بازگشتی 📣👨‍💻 @AlgorithmDesign_DataStructuer

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

درخت جست و جوی دودویی(BST): درخت جستجو دودویی یک درخت دودیی است که در آن هر گره از تمام کلید های زیر درخت چپ بزرگتر و از تمام کلید های زیر درخت راست کوچیک تر است. 📣👨‍💻 @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

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

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

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