۰
subtitle
ارسال: #۱
پیچیدگی زمانی
با سلام پیچیدگی زمان این حلقه چی میشه؟
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
}
x=x+1
n=n-1
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
}
x=x+1
n=n-1
{
۰
ارسال: #۲
پیچیدگی زمانی
سلام
به ازای i=1 جمله x=x+1 ء n/2 بار اجرا میشود
به ازای i=1 جمله x=x+1 ء n/4 بار اجرا میشود
به همین ترتیب : تعداد اجرای دستور x=x+1 .....،=>ء(.........n/2+n/4+n/8) که اگر از n فکتور بگیریم عبارت زیر بدست می آید:
n*((1/2)/(1-(1/2))=(....1/2+1/4+1/8)n......که متبه اجرایی آن میشود( تتا n)
به ازای i=1 جمله x=x+1 ء n/2 بار اجرا میشود
به ازای i=1 جمله x=x+1 ء n/4 بار اجرا میشود
به همین ترتیب : تعداد اجرای دستور x=x+1 .....،=>ء(.........n/2+n/4+n/8) که اگر از n فکتور بگیریم عبارت زیر بدست می آید:
n*((1/2)/(1-(1/2))=(....1/2+1/4+1/8)n......که متبه اجرایی آن میشود( تتا n)
۰
ارسال: #۳
پیچیدگی زمانی
سلام. پیچیدگیش از مرتبه n میشه. فکر کنم کمتر از n بار دستور داخل حلقه درونی اجرا بشه. چون مقدار n همینجوری کم میشه و قبل از اینکه به صفر برسه از i کمتر میشه و از حلقه خارج میشه. تعداد دفعات اجراش میشه حدود n-lgn که از مرتبه n میشه.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close