تالار گفتمان مانشت
سوال مفهومی ;-) از مرتبه زمانی - نسخه‌ی قابل چاپ
سوال مفهومی ;-) از مرتبه زمانی - majid10 - 02 آبان ۱۳۹۵ ۰۱:۴۶ ب.ظ

سلام خدمت عزیزانِ جااااان ، عارضم به خدمتتون که با توجه به تصویر [تصویر: 424646_ca4fab44a3972235b829c46ab2066283.jpg]
مرتبه زمانی با توجه به اینکه j از ۱ تا i تغییر میکنه و j هر بار در دو ضرب میشود پس میشود log i در مبنای ۲ و چون حلقه اولی i از یک تا اِن تغییر میکنه پس میشه سیگما یک تا اِن ، لوگ آی [FACE WITH TEARS OF JOY] حالا ما امتحان که بکنیم مثلن n رو برابر ۴ فرض کنیم i به ازای ۱ ، یکبار به ازای ۲ ، دوبار به ازای ۳ ، دوبار و به ازای ۴ سه بار دستور اجرا میشود که جمعن میشود ۸بار ولی اگه از حالت سیگما حل کنیم میشود جمع لگاریتم ۱تا ۴ که جمعش برابر ۸نمیشود ، چراااااااا؟ یکی نباید بشههههه؟




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

Sent from my Nexus 5 using Tapatalk

RE: سوال مفهومی ;-) از مرتبه زمانی - Jooybari - 02 آبان ۱۳۹۵ ۰۲:۱۵ ب.ظ

سلام. وقتتون بخیر.
جوابتون درسته. ولی توی لگاریتم باید اعشار رو حذف کنید. اگه تعداد دقیق j رو قصد دارید محاسبه کنید میشه [tex]\lfloor\lg\: i\rfloor+1[/tex]. این رو ما از مرتبه lgi میدونیم.

RE: سوال مفهومی ;-) از مرتبه زمانی - majid10 - 02 آبان ۱۳۹۵ ۱۰:۳۹ ب.ظ

(۰۲ آبان ۱۳۹۵ ۰۲:۱۵ ب.ظ)Jooybari نوشته شده توسط:  سلام. وقتتون بخیر.
جوابتون درسته. ولی توی لگاریتم باید اعشار رو حذف کنید. اگه تعداد دقیق j رو قصد دارید محاسبه کنید میشه [tex]\lfloor\lg\: i\rfloor+1[/tex]. این رو ما از مرتبه lgi میدونیم.
داداش متوجه منظورت نشدم میشه بیشتر توضیح بدیییییی ؟:-( اخه یه جواب میشه nlog n یکی دیگه میشه log n +1

RE: سوال مفهومی ;-) از مرتبه زمانی - Jooybari - 03 آبان ۱۳۹۵ ۱۲:۰۰ ق.ظ

(۰۲ آبان ۱۳۹۵ ۱۰:۳۹ ب.ظ)majid10 نوشته شده توسط:  
(02 آبان ۱۳۹۵ ۰۲:۱۵ ب.ظ)Jooybari نوشته شده توسط:  سلام. وقتتون بخیر.
جوابتون درسته. ولی توی لگاریتم باید اعشار رو حذف کنید. اگه تعداد دقیق j رو قصد دارید محاسبه کنید میشه [tex]\lfloor\lg\: i\rfloor+1[/tex]. این رو ما از مرتبه lgi میدونیم.
داداش متوجه منظورت نشدم میشه بیشتر توضیح بدیییییی ؟:-( اخه یه جواب میشه nlog n یکی دیگه میشه log n +1

منظورم اینه که جواب [tex]n lg n[/tex] و [tex]lg n +1[/tex] نمیشه. از مرتبه تتای این مقادیر میشه. تو تحلیل این رابطه میگیم جواب از مرتبه [tex]\theta(n lg n) [/tex] میشه. ولی مقدار دقیقش میشه:
[tex]\sum_{i=1}^n (\lfloor lg\: i\rfloor+1)[/tex]
اونجایی که جمع لگاریتم اعداد ۱ تا ۴ رو محاسبه کردی، حاصلجمع مقادیر [tex]\lfloor\lg\: i\rfloor+1[/tex] رو به ازای i از ۱ تا ۴ حساب کن. جواب یکی میشه.

RE: سوال مفهومی ;-) از مرتبه زمانی - majid10 - 05 آبان ۱۳۹۵ ۰۶:۰۳ ب.ظ

(۰۳ آبان ۱۳۹۵ ۱۲:۰۰ ق.ظ)Jooybari نوشته شده توسط:  
(02 آبان ۱۳۹۵ ۱۰:۳۹ ب.ظ)majid10 نوشته شده توسط:  
(02 آبان ۱۳۹۵ ۰۲:۱۵ ب.ظ)Jooybari نوشته شده توسط:  سلام. وقتتون بخیر.
جوابتون درسته. ولی توی لگاریتم باید اعشار رو حذف کنید. اگه تعداد دقیق j رو قصد دارید محاسبه کنید میشه [tex]\lfloor\lg\: i\rfloor+1[/tex]. این رو ما از مرتبه lgi میدونیم.
داداش متوجه منظورت نشدم میشه بیشتر توضیح بدیییییی ؟:-( اخه یه جواب میشه nlog n یکی دیگه میشه log n +1

منظورم اینه که جواب [tex]n lg n[/tex] و [tex]lg n +1[/tex] نمیشه. از مرتبه تتای این مقادیر میشه. تو تحلیل این رابطه میگیم جواب از مرتبه [tex]\theta(n lg n) [/tex] میشه. ولی مقدار دقیقش میشه:
[tex]\sum_{i=1}^n (\lfloor lg\: i\rfloor+1)[/tex]
اونجایی که جمع لگاریتم اعداد ۱ تا ۴ رو محاسبه کردی، حاصلجمع مقادیر [tex]\lfloor\lg\: i\rfloor+1[/tex] رو به ازای i از ۱ تا ۴ حساب کن. جواب یکی میشه.
دمت گرم داداش ، خیلی ممنون

Sent from my Nexus 5 using Tapatalk