۰
subtitle
ارسال: #۱
سوال مفهومی ;-) از مرتبه زمانی
سلام خدمت عزیزانِ جااااان ، عارضم به خدمتتون که با توجه به تصویر ![[تصویر: 424646_ca4fab44a3972235b829c46ab2066283.jpg]](https://img.manesht.ir/424646_ca4fab44a3972235b829c46ab2066283.jpg)
مرتبه زمانی با توجه به اینکه j از ۱ تا i تغییر میکنه و j هر بار در دو ضرب میشود پس میشود log i در مبنای ۲ و چون حلقه اولی i از یک تا اِن تغییر میکنه پس میشه سیگما یک تا اِن ، لوگ آی حالا ما امتحان که بکنیم مثلن n رو برابر ۴ فرض کنیم i به ازای ۱ ، یکبار به ازای ۲ ، دوبار به ازای ۳ ، دوبار و به ازای ۴ سه بار دستور اجرا میشود که جمعن میشود ۸بار ولی اگه از حالت سیگما حل کنیم میشود جمع لگاریتم ۱تا ۴ که جمعش برابر ۸نمیشود ، چراااااااا؟ یکی نباید بشههههه؟
همه این توضیحات تو شکل هستش
ممنون میشم جواب بدید
Sent from my Nexus 5 using Tapatalk
مرتبه زمانی با توجه به اینکه j از ۱ تا i تغییر میکنه و j هر بار در دو ضرب میشود پس میشود log i در مبنای ۲ و چون حلقه اولی i از یک تا اِن تغییر میکنه پس میشه سیگما یک تا اِن ، لوگ آی حالا ما امتحان که بکنیم مثلن n رو برابر ۴ فرض کنیم i به ازای ۱ ، یکبار به ازای ۲ ، دوبار به ازای ۳ ، دوبار و به ازای ۴ سه بار دستور اجرا میشود که جمعن میشود ۸بار ولی اگه از حالت سیگما حل کنیم میشود جمع لگاریتم ۱تا ۴ که جمعش برابر ۸نمیشود ، چراااااااا؟ یکی نباید بشههههه؟
همه این توضیحات تو شکل هستش
ممنون میشم جواب بدید
Sent from my Nexus 5 using Tapatalk
۱
ارسال: #۲
RE: سوال مفهومی ;-) از مرتبه زمانی
سلام. وقتتون بخیر.
جوابتون درسته. ولی توی لگاریتم باید اعشار رو حذف کنید. اگه تعداد دقیق j رو قصد دارید محاسبه کنید میشه [tex]\lfloor\lg\: i\rfloor+1[/tex]. این رو ما از مرتبه lgi میدونیم.
جوابتون درسته. ولی توی لگاریتم باید اعشار رو حذف کنید. اگه تعداد دقیق j رو قصد دارید محاسبه کنید میشه [tex]\lfloor\lg\: i\rfloor+1[/tex]. این رو ما از مرتبه lgi میدونیم.
ارسال: #۳
RE: سوال مفهومی ;-) از مرتبه زمانی
(۰۲ آبان ۱۳۹۵ ۰۲:۱۵ ب.ظ)Jooybari نوشته شده توسط: سلام. وقتتون بخیر.داداش متوجه منظورت نشدم میشه بیشتر توضیح بدیییییی ؟:-( اخه یه جواب میشه nlog n یکی دیگه میشه log n +1
جوابتون درسته. ولی توی لگاریتم باید اعشار رو حذف کنید. اگه تعداد دقیق j رو قصد دارید محاسبه کنید میشه [tex]\lfloor\lg\: i\rfloor+1[/tex]. این رو ما از مرتبه lgi میدونیم.
ارسال: #۴
RE: سوال مفهومی ;-) از مرتبه زمانی
(۰۲ آبان ۱۳۹۵ ۱۰:۳۹ ب.ظ)majid10 نوشته شده توسط:(02 آبان ۱۳۹۵ ۰۲:۱۵ ب.ظ)Jooybari نوشته شده توسط: سلام. وقتتون بخیر.داداش متوجه منظورت نشدم میشه بیشتر توضیح بدیییییی ؟:-( اخه یه جواب میشه nlog n یکی دیگه میشه log n +1
جوابتون درسته. ولی توی لگاریتم باید اعشار رو حذف کنید. اگه تعداد دقیق j رو قصد دارید محاسبه کنید میشه [tex]\lfloor\lg\: i\rfloor+1[/tex]. این رو ما از مرتبه lgi میدونیم.
منظورم اینه که جواب [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: سوال مفهومی ;-) از مرتبه زمانی
(۰۳ آبان ۱۳۹۵ ۱۲:۰۰ ق.ظ)Jooybari نوشته شده توسط:دمت گرم داداش ، خیلی ممنون(02 آبان ۱۳۹۵ ۱۰:۳۹ ب.ظ)majid10 نوشته شده توسط:(02 آبان ۱۳۹۵ ۰۲:۱۵ ب.ظ)Jooybari نوشته شده توسط: سلام. وقتتون بخیر.داداش متوجه منظورت نشدم میشه بیشتر توضیح بدیییییی ؟:-( اخه یه جواب میشه nlog n یکی دیگه میشه log n +1
جوابتون درسته. ولی توی لگاریتم باید اعشار رو حذف کنید. اگه تعداد دقیق j رو قصد دارید محاسبه کنید میشه [tex]\lfloor\lg\: i\rfloor+1[/tex]. این رو ما از مرتبه lgi میدونیم.
منظورم اینه که جواب [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
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
 |
سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ | Azadam | ۶ | ۴,۸۸۴ |
۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ آخرین ارسال: Soldier's life |
| مرتبه ایجاد درخت | rad.bahar | ۱ | ۳,۳۷۱ |
۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar |
|
| مرتبه شبه کد | rad.bahar | ۱ | ۲,۳۳۳ |
۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ آخرین ارسال: BBumir |
|
| حل مساله مرتبه زمانی حلقه های تو در تو | sarashahi | ۱۶ | ۲۲,۹۶۲ |
۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ آخرین ارسال: gillda |
|
| مرتبه زمانی | Sanazzz | ۱۷ | ۲۱,۵۵۱ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ آخرین ارسال: mohsentafresh |
|
| پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت | اsepid8994 | ۰ | ۱,۷۸۶ |
۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ آخرین ارسال: اsepid8994 |
|
| مرتبه زمانی یافتن قطر | Sepideh96 | ۲ | ۳,۸۰۱ |
۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30 |
|
| مرتبه مانی | Sanazzz | ۳ | ۳,۷۱۶ |
۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ آخرین ارسال: Sanazzz |
|
 |
یافتن دو عدد پیچیدگی زمانی O(n) | porseshgar | ۲ | ۳,۹۳۴ |
۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ آخرین ارسال: porseshgar |
| مرتبه زمانی | Sanazzz | ۰ | ۲,۰۳۹ |
۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ آخرین ارسال: Sanazzz |
|
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close