سلام دوستان خیلی ممنون میشم واسه حل این مسئله کمک کنید..
سوال : تعداد تکرار عبارت ;++x در دو تکه کد زیر چیست؟ (البته به صورت جداگانه)
کد:
۱)
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++;کد:
۲)
for(i=1;i<=5;i++)
for(j=i;j<=n;j++)
for(k=j;k<=n;k++)
x++;بنده درس طراحی رو این ترم برداشتم واسه همین یکم گیج میزنم البته تو حلقه های وابسته اینطوریه...
دوستانی که لطف میکنند راهنمایی می کنند لطفا با فرمول و اینا بگن که متوجه بشم...
مرسی
سلام. به نظر من روش حل اینطوریه . چون حلقه اول از ۱ تا n بار اجرا میشه تعداد مراحل اجراش n هست. حلقه دوم هم چون حداکثر تا n بار میتونه اجرا بشه اینم n بار اجرا میشه و حلقه سوم هم همینطور. پس کل پیچیدگی زمانی تکه کد اول برابر [tex]O ( n^3 )[/tex]
هست. تکه کد دومی هم چون برنامه به تعداد محدودی اجرا میشه از مرتبه [tex]O ( 1 )[/tex]
هست.
برای حل اولی از طریق سیگما هم میتونبن به نتیجه برسین.
من دومی رو با سیگما حل کردم
[tex]\sum_{i=1}^{5}\sum_{j=i}^{n}\sum_{k=j}^{n}1[/tex]
اینو حل کنید میبینید که [tex]O(n^{2})[/tex]
شما هم حساب کنید ببینید همینو بدست میارید
دوستان خیلی ممنون ،
منم تونستم با سیگما حلش کنم...
جواب نهایی هم
(n(n+1)(2n+1))/6
میشه..
(۱۷ مهر ۱۳۹۲ ۰۳:۲۰ ب.ظ)pr0tector نوشته شده توسط: دوستان خیلی ممنون ،این جواب دومی هست؟
منم تونستم با سیگما حلش کنم...
جواب نهایی هم
(n(n+1)(2n+1))/6
میشه..
آخه دومی نمیتونه از [tex]O(n^2)[/tex] بیشتر بشه که!
(۱۶ مهر ۱۳۹۲ ۰۶:۱۰ ب.ظ)nazanin_sh نوشته شده توسط: من دومی رو با سیگما حل کردم
[tex]\sum_{i=1}^{5}\sum_{j=i}^{n}\sum_{k=j}^{n}1[/tex]
اینو حل کنید میبینید که [tex]O(n^{2})[/tex]
شما هم حساب کنید ببینید همینو بدست میارید
پس جواب تابع اول همون جوابیه که من نوشتم. واسه دومی هم به احتمال زیاد جواب شما درست باشه.
(۱۷ مهر ۱۳۹۲ ۰۳:۳۶ ب.ظ)nazanin_sh نوشته شده توسط: این جواب دومی هست؟
آخه دومی نمیتونه از [tex]O(n^2)[/tex] بیشتر بشه که!
چرا نتونه بیشتر از [tex]O(n^2)[/tex] بشه ؟
میشه راه حلتون از طریق سیگما اینجا بنویسید
(۲۲ مهر ۱۳۹۲ ۰۱:۲۳ ق.ظ)reza6966 نوشته شده توسط: چرا نتونه بیشتر از [tex]O(n^2)[/tex] بشه ؟
میشه راه حلتون از طریق سیگما اینجا بنویسید
توی پستای قبلی نوشتم .
[tex]\sum_{i=1}^{5}\sum_{j=i}^{n}\sum_{k=j}^{n}1[/tex]
اگه توجه کنید دوتا سیگما داره که حد بالاشون n هست و سیگمای سوم محدوده . بنابراین نهایتا [tex]O(n^2)[/tex] میشه.
(۲۳ مهر ۱۳۹۲ ۰۶:۱۳ ب.ظ)nazanin_sh نوشته شده توسط:(22 مهر ۱۳۹۲ ۰۱:۲۳ ق.ظ)reza6966 نوشته شده توسط: چرا نتونه بیشتر از [tex]O(n^2)[/tex] بشه ؟
میشه راه حلتون از طریق سیگما اینجا بنویسید
توی پستای قبلی نوشتم .
[tex]\sum_{i=1}^{5}\sum_{j=i}^{n}\sum_{k=j}^{n}1[/tex]
اگه توجه کنید دوتا سیگما داره که حد بالاشون n هست و سیگمای سوم محدوده . بنابراین نهایتا [tex]O(n^2)[/tex] میشه.
آها من فکر کردم در حالت کلی و موقعی که حدود i بین ۱ تا n باشه جوابتون [tex]O(n^2)[/tex] هست