تالار گفتمان مانشت
کامپیوتر ۸۷، محاسبه پیچیدگی - نسخه‌ی قابل چاپ
کامپیوتر ۸۷، محاسبه پیچیدگی - hoomanab - 10 بهمن ۱۳۹۲ ۱۲:۰۰ ب.ظ

سلام. لطفا دوستان راهنمایی کنند
سوال ۱۸
[تصویر: 243257_e8u8y3uz.jpg]

Sent from my SM-T210R using Tapatalk

RE: کامپیوتر ۸۷، محاسبه پیچیدگی - izadan11 - 10 بهمن ۱۳۹۲ ۰۷:۰۹ ب.ظ

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

RE: کامپیوتر ۸۷، محاسبه پیچیدگی - hoomanab - 10 بهمن ۱۳۹۲ ۰۹:۲۸ ب.ظ

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

Sent from my SM-T210R using Tapatalk

RE: کامپیوتر ۸۷، محاسبه پیچیدگی - izadan11 - 10 بهمن ۱۳۹۲ ۱۰:۰۴ ب.ظ

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

Sent from my SM-T210R using Tapatalk

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

RE: کامپیوتر ۸۷، محاسبه پیچیدگی - hoomanab - 10 بهمن ۱۳۹۲ ۱۰:۰۶ ب.ظ

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

Sent from my SM-T210R using Tapatalk

RE: کامپیوتر ۸۷، محاسبه پیچیدگی - izadan11 - 10 بهمن ۱۳۹۲ ۱۰:۳۸ ب.ظ

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

Sent from my SM-T210R using Tapatalk

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

RE: کامپیوتر ۸۷، محاسبه پیچیدگی - hoomanab - 10 بهمن ۱۳۹۲ ۱۱:۴۱ ب.ظ

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

Sent from my SM-T210R using Tapatalk

RE: کامپیوتر ۸۷، محاسبه پیچیدگی - minami - 10 بهمن ۱۳۹۲ ۱۱:۵۲ ب.ظ

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


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


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


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


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


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

RE: کامپیوتر ۸۷، محاسبه پیچیدگی - hoomanab - 11 بهمن ۱۳۹۲ ۱۲:۵۱ ق.ظ

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

Sent from my SM-T210R using Tapatalk
اینطور نمیشه که مرتب کرد. چون مینیمم از یک درایه به بعد باید محسابه شه. اگه اول مرتب کنیم، جواب تغییر میکنه

Sent from my SM-T210R using Tapatalk

RE: کامپیوتر ۸۷، محاسبه پیچیدگی - minami - 11 بهمن ۱۳۹۲ ۰۲:۱۹ ب.ظ

(۱۱ بهمن ۱۳۹۲ ۱۲:۵۱ ق.ظ)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میشه.

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

RE: کامپیوتر ۸۷، محاسبه پیچیدگی - hoomanab - 11 بهمن ۱۳۹۲ ۰۳:۲۸ ب.ظ

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

Sent from my SM-T210R using Tapatalk

RE: کامپیوتر ۸۷، محاسبه پیچیدگی - minami - 11 بهمن ۱۳۹۲ ۰۳:۴۱ ب.ظ

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

Sent from my SM-T210R using Tapatalk


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

RE: کامپیوتر ۸۷، محاسبه پیچیدگی - hoomanab - 11 بهمن ۱۳۹۲ ۰۵:۳۸ ب.ظ

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

Sent from my SM-T210R using Tapatalk