۰
subtitle
ارسال: #۱
پیچیدگی زمانی ۳ حلقه for تودرتوی وابسته
سلام دوستان خیلی ممنون میشم واسه حل این مسئله کمک کنید..
سوال : تعداد تکرار عبارت ;++x در دو تکه کد زیر چیست؟ (البته به صورت جداگانه)
بنده درس طراحی رو این ترم برداشتم واسه همین یکم گیج میزنم البته تو حلقه های وابسته اینطوریه...
دوستانی که لطف میکنند راهنمایی می کنند لطفا با فرمول و اینا بگن که متوجه بشم...
مرسی
سوال : تعداد تکرار عبارت ;++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++;بنده درس طراحی رو این ترم برداشتم واسه همین یکم گیج میزنم البته تو حلقه های وابسته اینطوریه...
دوستانی که لطف میکنند راهنمایی می کنند لطفا با فرمول و اینا بگن که متوجه بشم...
مرسی
۰
ارسال: #۲
RE: پیچیدگی زمانی ۳ حلقه for تودرتوی وابسته
سلام. به نظر من روش حل اینطوریه . چون حلقه اول از ۱ تا n بار اجرا میشه تعداد مراحل اجراش n هست. حلقه دوم هم چون حداکثر تا n بار میتونه اجرا بشه اینم n بار اجرا میشه و حلقه سوم هم همینطور. پس کل پیچیدگی زمانی تکه کد اول برابر [tex]O ( n^3 )[/tex]
هست. تکه کد دومی هم چون برنامه به تعداد محدودی اجرا میشه از مرتبه [tex]O ( 1 )[/tex]
هست.
برای حل اولی از طریق سیگما هم میتونبن به نتیجه برسین.
هست. تکه کد دومی هم چون برنامه به تعداد محدودی اجرا میشه از مرتبه [tex]O ( 1 )[/tex]
هست.
برای حل اولی از طریق سیگما هم میتونبن به نتیجه برسین.
۰
ارسال: #۳
RE: پیچیدگی زمانی ۳ حلقه for تودرتوی وابسته
من دومی رو با سیگما حل کردم
[tex]\sum_{i=1}^{5}\sum_{j=i}^{n}\sum_{k=j}^{n}1[/tex]
اینو حل کنید میبینید که [tex]O(n^{2})[/tex]
شما هم حساب کنید ببینید همینو بدست میارید
[tex]\sum_{i=1}^{5}\sum_{j=i}^{n}\sum_{k=j}^{n}1[/tex]
اینو حل کنید میبینید که [tex]O(n^{2})[/tex]
شما هم حساب کنید ببینید همینو بدست میارید
ارسال: #۴
RE: پیچیدگی زمانی ۳ حلقه for تودرتوی وابسته
(۱۶ مهر ۱۳۹۲ ۰۶:۱۰ ب.ظ)nazanin_sh نوشته شده توسط: من دومی رو با سیگما حل کردم
[tex]\sum_{i=1}^{5}\sum_{j=i}^{n}\sum_{k=j}^{n}1[/tex]
اینو حل کنید میبینید که [tex]O(n^{2})[/tex]
شما هم حساب کنید ببینید همینو بدست میارید
پس جواب تابع اول همون جوابیه که من نوشتم. واسه دومی هم به احتمال زیاد جواب شما درست باشه.
۰
ارسال: #۵
RE: پیچیدگی زمانی ۳ حلقه for تودرتوی وابسته
دوستان خیلی ممنون ،
منم تونستم با سیگما حلش کنم...
جواب نهایی هم
(n(n+1)(2n+1))/6
میشه..
منم تونستم با سیگما حلش کنم...
جواب نهایی هم
(n(n+1)(2n+1))/6
میشه..
ارسال: #۶
RE: پیچیدگی زمانی ۳ حلقه for تودرتوی وابسته
ارسال: #۷
RE: پیچیدگی زمانی ۳ حلقه for تودرتوی وابسته
ارسال: #۸
RE: پیچیدگی زمانی ۳ حلقه for تودرتوی وابسته
(۲۲ مهر ۱۳۹۲ ۰۱:۲۳ ق.ظ)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] میشه.
ارسال: #۹
RE: پیچیدگی زمانی ۳ حلقه for تودرتوی وابسته
(۲۳ مهر ۱۳۹۲ ۰۶:۱۳ ب.ظ)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] هست
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close