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

پیچیدگی زمان اجرا- قدسی

ارسال:
  

dokhtare payiz پرسیده:

پیچیدگی زمان اجرا- قدسی

راه حلشو احساس میکنم اشتباه کرده


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

Pure Liveliness پاسخ داده:

RE: پیچیدگی زمان اجرا- قدسی

سلام. اگه منظورتون سوالی باشه که کنارش * زدید:
ورودی با اندازه ی ۱۰۰ *۱ => ۶ثانیه = ۶*(۲^۱)
ورودی با اندازه ی ۱۰۰*۱۰ => ۶*۱۰۰ثانیه =۶۰۰ثانیه = ۶*(۲^۱۰)
ورودی با اندازه ی ۱۰۰*۱۰۰ => ۶*۱۰۰۰۰ثانیه =۶۰۰۰۰ثانیه = ۶(۲^۱۰۰)
.
.
input= 100*(10^n) -> output=6*(10^n)^2
output = teta(n^2 اندازه ی ورودی= n

جمله ی اول دنباله ۱۰۰ هست. مقدار بقیه ی جملات رو به صورت ۱۰۰ ضربدر یه چیزی مینویسیم و حساب میکنیم. این طوری میبینیم که هر جمله به صورت ۶ضربدر (ضریب ۱۰۰ توی ورودی به توان ۲) میشه. چون این ۱۰۰ توی همه شون ثابت هست پس توی پیچیدگی اثر نداره.
نقل قول این ارسال در یک پاسخ

ارسال:
  

dokhtare payiz پاسخ داده:

RE: پیچیدگی زمان اجرا- قدسی

(۲۹ اردیبهشت ۱۳۹۵ ۰۱:۰۸ ق.ظ)pure liveliness نوشته شده توسط:  سلام. اگه منظورتون سوالی باشه که کنارش * زدید:
ورودی با اندازه ی ۱۰۰ *۱ => ۶ثانیه = ۶*(۲^۱)
ورودی با اندازه ی ۱۰۰*۱۰ => ۶*۱۰۰ثانیه =۶۰۰ثانیه = ۶*(۲^۱۰)
ورودی با اندازه ی ۱۰۰*۱۰۰ => ۶*۱۰۰۰۰ثانیه =۶۰۰۰۰ثانیه = ۶(۲^۱۰۰)
.
.
input= 100*(10^n) -> output=6*(10^n)^2
output = teta(n^2 اندازه ی ورودی= n

جمله ی اول دنباله ۱۰۰ هست. مقدار بقیه ی جملات رو به صورت ۱۰۰ ضربدر یه چیزی مینویسیم و حساب میکنیم. این طوری میبینیم که هر جمله به صورت ۶ضربدر (ضریب ۱۰۰ توی ورودی به توان ۲) میشه. چون این ۱۰۰ توی همه شون ثابت هست پس توی پیچیدگی اثر نداره.
آهان مرسی
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Saman پاسخ داده:

RE: پیچیدگی زمان اجرا- قدسی

سلام
در حالت کلی برای حل این سوال به شکل زیر عمل میکنیم :
تعداد ورودی ها را با توانی خاص در نظر میگیریم(دقت کنید که این توان گاهی یک و چند جمله ای می باشد).
چرا؟
ما پاسخ ورودی ها را با مدت خاصی از زمان میدهیم،محاسبه ی این مدت پاسخ مساله خواهد بود.

[tex]100^x\cong6\sec\Longrightarrow\: 1000^x=10^x\times100^x\cong600\sec\: =10^2\times6\sec\Longrightarrow\: x=2[/tex]
در واقع x=2 توان مرتبه ی رشد است و این یعنی با توجه به زمان پاسخ به این مقدار از ورودی ما در یک مرتبه ی درجه ی دوم از رشد میتوانیم به این میزان از اندازه های ورودی پاسخ دهیم.
نکته :وقتی اندازه ی ورودی در کنار زمان اجرا قرار میگیرد میتوان مرتبه ی رشد را محاسبه کرد و نباید با توجه به اندازه ی ثابت ورودی ها مرتبه را [tex]O(1)[/tex] فرض کرد!!

با تاکید بسیار به دنبال کننده ها : به بررسی سوالات ۵۰-۱ و ۵۲-۱ نیز بپردازید که مساله واضح تر شود.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  درخواست تصحیح (تعویق) زمان کنکور ارشد ۱۴۰۱ s.gg ۱ ۱۴ ۲۳ بهمن ۱۴۰۱ ۰۷:۴۳ ب.ظ
آخرین ارسال: HamidReza1
  تعویق زمان کنکور ارشد sima84 ۰ ۱,۴۷۳ ۱۸ اردیبهشت ۱۴۰۰ ۰۱:۰۵ ب.ظ
آخرین ارسال: sima84
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۵۶۸ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
Exclamation زمان برگزاری کنکور ارشد ۹۸ به تعویق افتاد elect ۲ ۲,۶۴۱ ۱۳ مهر ۱۳۹۸ ۰۵:۲۴ ب.ظ
آخرین ارسال: saharfarhang
Question یافتن دو عدد پیچیدگی زمانی O(n) porseshgar ۲ ۳,۵۰۶ ۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ
آخرین ارسال: porseshgar
  تعیین زمان سفارت کشور فرانسه zpv1234 ۰ ۲,۰۶۶ ۲۱ شهریور ۱۳۹۷ ۰۱:۴۸ ب.ظ
آخرین ارسال: zpv1234
  مشکل در پیچیدگی زمانی ماهی ۲۵۸ ۲ ۲,۷۳۶ ۲۳ تیر ۱۳۹۷ ۱۲:۱۸ ق.ظ
آخرین ارسال: Alisalar
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) Saman ۶ ۶,۸۱۴ ۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ
آخرین ارسال: saeed_vahidi
  الگوریتم SRT زمانبندی کوتاه ترین زمان باقی مانده Happiness.72 ۶ ۱۷,۰۲۲ ۲۴ خرداد ۱۳۹۷ ۰۷:۵۷ ب.ظ
آخرین ارسال: amirjo0on

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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