زمان کنونی: ۱۱ آبان ۱۴۰۳, ۰۷:۰۱ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

کامپیوتر ۸۷، محاسبه پیچیدگی

ارسال:
  

hoomanab پرسیده:

کامپیوتر ۸۷، محاسبه پیچیدگی

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

Sent from my SM-T210R using Tapatalk
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

izadan11 پاسخ داده:

RE: کامپیوتر ۸۷، محاسبه پیچیدگی

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

۰
ارسال:
  

hoomanab پاسخ داده:

RE: کامپیوتر ۸۷، محاسبه پیچیدگی

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

Sent from my SM-T210R using Tapatalk
نقل قول این ارسال در یک پاسخ

ارسال:
  

izadan11 پاسخ داده:

RE: کامپیوتر ۸۷، محاسبه پیچیدگی

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

Sent from my SM-T210R using Tapatalk

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

۰
ارسال:
  

hoomanab پاسخ داده:

RE: کامپیوتر ۸۷، محاسبه پیچیدگی

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

Sent from my SM-T210R using Tapatalk
نقل قول این ارسال در یک پاسخ

ارسال:
  

izadan11 پاسخ داده:

RE: کامپیوتر ۸۷، محاسبه پیچیدگی

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

Sent from my SM-T210R using Tapatalk

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

۰
ارسال:
  

hoomanab پاسخ داده:

RE: کامپیوتر ۸۷، محاسبه پیچیدگی

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

Sent from my SM-T210R using Tapatalk
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

minami پاسخ داده:

RE: کامپیوتر ۸۷، محاسبه پیچیدگی

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


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


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


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


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


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

۰
ارسال:
  

hoomanab پاسخ داده:

RE: کامپیوتر ۸۷، محاسبه پیچیدگی

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

Sent from my SM-T210R using Tapatalk

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

Sent from my SM-T210R using Tapatalk
نقل قول این ارسال در یک پاسخ

ارسال: #۱۰
  

minami پاسخ داده:

RE: کامپیوتر ۸۷، محاسبه پیچیدگی

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

آره ۶۰۰ اشتباهه راه حلش.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۱
  

hoomanab پاسخ داده:

RE: کامپیوتر ۸۷، محاسبه پیچیدگی

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

Sent from my SM-T210R using Tapatalk
نقل قول این ارسال در یک پاسخ

ارسال: #۱۲
  

minami پاسخ داده:

RE: کامپیوتر ۸۷، محاسبه پیچیدگی

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

Sent from my SM-T210R using Tapatalk


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

۰
ارسال: #۱۳
  

hoomanab پاسخ داده:

RE: کامپیوتر ۸۷، محاسبه پیچیدگی

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

Sent from my SM-T210R using Tapatalk
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۸,۰۳۰ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۷۷۶ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
  نحوه محاسبه دفیق لگاریتم بدون ماشین حساب mcse2010 ۲ ۸۲,۱۲۳ ۲۸ مهر ۱۳۹۸ ۰۹:۳۸ ق.ظ
آخرین ارسال: chemical_darton29
  محاسبه تراز معدل موثر از رشته آی تی یا علوم کامپیوتر به مهندسی کامپیوتر یا بالعکس gnulinux ۰ ۲,۵۰۱ ۲۱ شهریور ۱۳۹۸ ۰۸:۳۷ ق.ظ
آخرین ارسال: gnulinux
Question یافتن دو عدد پیچیدگی زمانی O(n) porseshgar ۲ ۳,۹۰۴ ۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ
آخرین ارسال: porseshgar
  تقسیم برای محاسبه کد افزونه چرخشی (CRC) Sanazzz ۴ ۶,۸۵۹ ۲۰ آذر ۱۳۹۷ ۰۱:۱۸ ب.ظ
آخرین ارسال: Sanazzz
  محاسبه چندمین عنصر آرایه Mr.R3ZA ۶ ۶,۶۷۴ ۱۹ شهریور ۱۳۹۷ ۰۸:۱۲ ب.ظ
آخرین ارسال: Saman
  مشکل در پیچیدگی زمانی ماهی ۲۵۸ ۲ ۲,۹۹۸ ۲۳ تیر ۱۳۹۷ ۱۲:۱۸ ق.ظ
آخرین ارسال: Alisalar
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) Saman ۶ ۷,۴۳۹ ۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ
آخرین ارسال: saeed_vahidi
  نحوه محاسبه مجموعه پیش بینی یا lookahead Erfan_Ekh ۱ ۲,۵۶۲ ۲۷ خرداد ۱۳۹۷ ۰۱:۳۱ ق.ظ
آخرین ارسال: ftmbghrn

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close