ما اول آرایه m رو مرتب می کنیم میشه m log m
بعد اعضای آرایی n رو یکی یکی تو m سرچ می کنیم اگر تکراری نبود اضافه می کنیم و آخر سر کل m رو اضافه n log m
پس گزینه ی ۴

جواب سنجش گزینه ۳ هست

Sent from my SM-T210R using Tapatalk

(۱۰ بهمن ۱۳۹۲ ۰۹:۲۸ ب.ظ)hoomanab نوشته شده توسط:  جواب سنجش گزینه ۳ هست

Sent from my SM-T210R using Tapatalk

وقتی راه حل با پیچیدگی کمتر هست پیچیدگی بالاتر قابل قبول نیست
سنجش اشتباه کرده

اشتباهتون اینجاست که مرتب کردن آرایه mlogm نمیشه. اگه دقت کنید میبینید که اون قسمتی که میخوایم ازش استفاده کنیم، طولش n-m+1 هست نه m.

Sent from my SM-T210R using Tapatalk

(۱۰ بهمن ۱۳۹۲ ۱۰:۰۶ ب.ظ)hoomanab نوشته شده توسط:  اشتباهتون اینجاست که مرتب کردن آرایه mlogm نمیشه. اگه دقت کنید میبینید که اون قسمتی که میخوایم ازش استفاده کنیم، طولش n-m+1 هست نه m.

Sent from my SM-T210R using Tapatalk

منظورت رو نفهمیدم
ما آرایه ی کوچکتر رو مرتب میکنیم پس m log m رو داریم

کل آرایه تقسیم میشه به دو قسمت. قسمت اول به اندازه n-m+1 و قسمت دوم به اندازه m-1.
جوابی که مسیله میخواد، مربوط به قسمت اول آرایه هست

Sent from my SM-T210R using Tapatalk

فک کنم، ایشون دارن سئوال ۱۹ رو جواب میدن!


این جواب پارسه:


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


اینم جواب ۶۰۰ مسئله:


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


ولی من فکر میکنم جواب پارسه درسته و ۶۰۰ فقط واسه حالتی که آرایه مرتب صعودی باشه، جواب میده و مینیمم رو از اول حساب میکنه، نظر شما چیه ؟

چرا هر عنصر، با m-1 عنصر مقایسه میشه؟!

Sent from my SM-T210R using Tapatalk

---

اینطور نمیشه که مرتب کرد. چون مینیمم از یک درایه به بعد باید محسابه شه. اگه اول مرتب کنیم، جواب تغییر میکنه

Sent from my SM-T210R using Tapatalk

(۱۱ بهمن ۱۳۹۲ ۱۲:۵۱ ق.ظ)hoomanab نوشته شده توسط:  چرا هر عنصر، با m-1 عنصر مقایسه میشه؟!

Sent from my SM-T210R using Tapatalk

---

اینطور نمیشه که مرتب کرد. چون مینیمم از یک درایه به بعد باید محسابه شه. اگه اول مرتب کنیم، جواب تغییر میکنه

Sent from my SM-T210R using Tapatalk

چون هر خونه آرایه mins باید مینیمم بین m-1 عنصر باشه و تعداد خونه هاشم n-m-1 که چون n/2>m، تعداد خونه هاش از n/2 بیشتر هست و واسه هر خونه m-1 مقایسه داشته باشیم، که از مرتبه nmمیشه.

آره ۶۰۰ اشتباهه راه حلش.

یعنی چی؟! مگه مقایسه رو از خونه ۱ تا n-m+1 انجام نمیدیم؟!

Sent from my SM-T210R using Tapatalk

(۱۱ بهمن ۱۳۹۲ ۰۳:۲۸ ب.ظ)hoomanab نوشته شده توسط:  یعنی چی؟! مگه مقایسه رو از خونه ۱ تا n-m+1 انجام نمیدیم؟!

Sent from my SM-T210R using Tapatalk

نه ، برای هر خونه ی mins از اون اندیس تا m-1 تا خونه بعدش مقایسه میکنیم، تعریف آرایه mins رو ببینید

نمیدونم چرا یه n اضافی دیدم

Sent from my SM-T210R using Tapatalk