یک جزوه بسیار خوب از پیچیدگی زمانی توابع مهم که می توانید پیچدگی زمانی را بیشتر درک کنید و اینکه چرا پیچیدگی زمانی اینقدر مهم هستند؟!
میتوانیم در زندگی روزمره هم از آن ها استفاده کنید که سریع تر به هدفمون برسیم.

لطفا برای کسانی که علاقمند هستن و دوست دارند اطلاع مفیدی در این زمینه داشته باشن بفرستید.تشکر😁🙏

📣👨‍💻 @AlgorithmDesign_DataStructuer

#پاسخ_تشریحی
با استفاده از تغیر متغییر میتوان آن را حل کرد که اگر بعد از استفاده از تغییر متغیر با استفاده از قضیه Master که بدون در نظر گرفتن 1- میتوان جواب سوال را به دست آوریم.

📣👨‍💻 @AlgorithmDesign_DataStructuer

👈 مرتب سازی ادغام(Merge Sort) چگونه کار می کند؟

همانطور که می دانیم که مرتب‌سازی ادغام از قانون تقسیم برای شکستن مسئله به مسائل فرعی استفاده می‌کندکه می توان گفت از الگوریتم Divide-and-conquer استفاده می شود،که مشکل در این مورد مرتب کردن یک آرایه معین است.

در مرتب سازی ادغام، آرایه داده شده را در میانه راه می شکنیم، به عنوان مثال اگر آرایه اصلی 6 عنصر داشته باشد، مرتب سازی ادغامی آن را به دو زیرآرایه با 3 عنصر تقسیم می کند.

اما شکستن آرایه اصلی به 2 زیرآرایه کوچکتر به ما در مرتب سازی آرایه کمکی نمی کند.

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

و سپس باید تمام این زیرآرایه های مرتب شده را گام به گام با هم ادغام کنیم تا یک آرایه مرتب شده واحد تشکیل دهیم.

بیایید یک آرایه با مقادیر {14، 7، 3، 12، 9، 11، 6، 12} در نظر بگیریم.

در شکل بالا ما یک نمایش تصویری از نحوه مرتب‌سازی ادغام مرتب‌سازی آرایه داده‌شده داریم.

👈 در مرتب سازی ادغام مراحل زیر را انجام می دهیم:

یک متغیر p را می گیریم و شاخص شروع آرایه خود را در آن ذخیره می کنیم. و یک متغیر دیگر r را می گیریم و آخرین اندیس آرایه را در آن ذخیره می کنیم.
سپس وسط آرایه را با استفاده از p+rمیکنیم سپس حاصل را تقسیم بر 2 میکنیم که وسط آرایه مشخص را می کنیم و اندیس میانی را به صورت q مشخص می کنیم و آرایه را به دو زیرآرایه از p تا q و از q + 1 تا شاخص r تقسیم می کنیم.
سپس این 2 زیرآرایه را دوباره تقسیم می کنیم، همانطور که آرایه اصلی خود را تقسیم کردیم و این ادامه می یابد.
هنگامی که آرایه اصلی را به زیرآرایه هایی با عناصر تک تقسیم کردیم، سپس شروع به ادغام زیرآرایه ها می کنیم.


📣👨‍💻 @AlgorithmDesign_DataStructuer

الگوریتم کروسکال چگونه کار می کند؟

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

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

از الگوریتم کروسکال می توان برای چیدمان سیم کشی برق در بین شهرها استفاده کرد.
می توان از آن برای برقراری اتصالات LAN استفاده کرد.

به مثاال بالا توجه کنید.

📣👨‍💻 @AlgorithmDesign_DataStructuer

اثبات 3 شرط قیضه Master


📣👨‍💻 @AlgorithmDesign_DataStructuer