راه حلشو احساس میکنم اشتباه کرده
سلام
در حالت کلی برای حل این سوال به شکل زیر عمل میکنیم :
تعداد ورودی ها را با توانی خاص در نظر میگیریم(دقت کنید که این توان گاهی یک و چند جمله ای می باشد).
چرا؟
ما پاسخ ورودی ها را با مدت خاصی از زمان میدهیم،محاسبه ی این مدت پاسخ مساله خواهد بود.
[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] فرض کرد!!
با تاکید بسیار به دنبال کننده ها : به بررسی سوالات ۵۰-۱ و ۵۲-۱ نیز بپردازید که مساله واضح تر شود.
سلام. اگه منظورتون سوالی باشه که کنارش * زدید:
ورودی با اندازه ی ۱۰۰ *۱ => ۶ثانیه = ۶*(۲^۱)
ورودی با اندازه ی ۱۰۰*۱۰ => ۶*۱۰۰ثانیه =۶۰۰ثانیه = ۶*(۲^۱۰)
ورودی با اندازه ی ۱۰۰*۱۰۰ => ۶*۱۰۰۰۰ثانیه =۶۰۰۰۰ثانیه = ۶(۲^۱۰۰)
.
.
input= 100*(10^n) -> output=6*(10^n)^2
output = teta(n^2 اندازه ی ورودی= n
جمله ی اول دنباله ۱۰۰ هست. مقدار بقیه ی جملات رو به صورت ۱۰۰ ضربدر یه چیزی مینویسیم و حساب میکنیم. این طوری میبینیم که هر جمله به صورت ۶ضربدر (ضریب ۱۰۰ توی ورودی به توان ۲) میشه. چون این ۱۰۰ توی همه شون ثابت هست پس توی پیچیدگی اثر نداره.
(۲۹ اردیبهشت ۱۳۹۵ ۰۱:۰۸ ق.ظ)pure liveliness نوشته شده توسط: سلام. اگه منظورتون سوالی باشه که کنارش * زدید:آهان مرسی
ورودی با اندازه ی ۱۰۰ *۱ => ۶ثانیه = ۶*(۲^۱)
ورودی با اندازه ی ۱۰۰*۱۰ => ۶*۱۰۰ثانیه =۶۰۰ثانیه = ۶*(۲^۱۰)
ورودی با اندازه ی ۱۰۰*۱۰۰ => ۶*۱۰۰۰۰ثانیه =۶۰۰۰۰ثانیه = ۶(۲^۱۰۰)
.
.
input= 100*(10^n) -> output=6*(10^n)^2
output = teta(n^2 اندازه ی ورودی= n
جمله ی اول دنباله ۱۰۰ هست. مقدار بقیه ی جملات رو به صورت ۱۰۰ ضربدر یه چیزی مینویسیم و حساب میکنیم. این طوری میبینیم که هر جمله به صورت ۶ضربدر (ضریب ۱۰۰ توی ورودی به توان ۲) میشه. چون این ۱۰۰ توی همه شون ثابت هست پس توی پیچیدگی اثر نداره.