Printable View
سلام
order تابع زیر چنده
for(i=1;i<=n;i++)
for(j=1;j<=i/2,j++)
{
----
----
for(k=1;k<13;k++)
{
----
}
----
}
o(n^2)
ضریب مخفی
order = 1/2 n^2 یا order = 13/2 n^2
سوالم اینه که در محاسبه ضریب مخفی oerder تابع ؛ سومین for که به تعداد محدودی
اجرا میشه باید در نظر گرفته بشود یا خیر
ممنون
حلقه اولی nو حلقه دومی lognو حلقه سومی 13 بار انجام میشه. و عدد ثابت رو میشه نادیده گرفت. که اگه اشتباه نکرده باشم کلش میشه nlogn
به نظر من هم از مرتبه nlog n هست.
سلام
order که همون n^2 هستش نه nlogn
سوالم اینه که for سومی در ضریب مخفی تاثیر داره یا نه؟
میشه توضیح بدی چرا nlognنیست؟نقل قول:
نوشته شده توسط mahdi bg
سلام
logn زمانی ساخته میشه که همچین چیزی داشته باشیمنقل قول:
نوشته شده توسط lvenoos
for(i=1;i<=n;i=(i*2))
یا
for(i=n;i>1;i=(i/2))
نه مثل کد بالا که i یکی یکی اضافه میشه
همون طور که گفتم مشکلم در مورد for سومی که آیا 13 با تکرارش
در ضریب مخفی تاثیر داره یا نه؟
می خواهید چی را بدست بیاورید؟ اگه O هست جواب سوال منفی هست ولی اگه تتا باشه تاثیر دارهنقل قول:
سوالم اینه که for سومی در ضریب مخفی تاثیر داره یا نه؟
سلام
منظورم دقیقا تتا بود می خواستم بدونم در محاسبه تتا باید 13 رو تاثیر
بدم یا اینه که تمام اون قسمت ها رو با تتا برابر یک حل کنم
ممنون
بله حق با شماست:
∑(i=1 to n) ∑(j:=1 to i/2) 1 = 1/2 ∑ (i=1 to n) I =1/2 * n(n+1)/2 => O(n^2)و در مورد تاثیر حلقه سوم:
n^2 < 13/4 *(n^2 +n) <100 n^2 => g(n)=n^2 => f(n)= teta(n^2)اما اگر تاثیر حلقه سوم را در نظر نگیریم :
در نتیجه میتوان گفت که حلقه سوم در محاسبه تتا اثرگذار است.
نمیتواندN^2 < 1/4 *(n^2 +n) <100 n^2 => f(n)= O(n^2)
این حلقه که فقط داره تعداد عملیات رو در ضریب ثابتی ضرب می کنه...با توجه به تعریف این تابع همه چیش(!) همون n^2 می شه.
یعنی هم O هم omega هم teta (البته از نوع capital ش)