یک سوال در مورد محاسبه order

[mahdi bg]

سلام
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 که به تعداد محدودی
اجرا میشه باید در نظر گرفته بشود یا خیر
ممنون

[lvenoos]

حلقه اولی nو حلقه دومی lognو حلقه سومی 13 بار انجام میشه. و عدد ثابت رو میشه نادیده گرفت. که اگه اشتباه نکرده باشم کلش میشه nlogn

[rezvan_DP]

به نظر من هم از مرتبه nlog n هست.

[mahdi bg]

سلام
order که همون n^2 هستش نه nlogn
سوالم اینه که for سومی در ضریب مخفی تاثیر داره یا نه؟

[lvenoos]

سلام
order که همون n^2 هستش نه nlogn
سوالم اینه که for سومی در ضریب مخفی تاثیر داره یا نه؟

میشه توضیح بدی چرا nlognنیست؟

[mahdi bg]

سلام

میشه توضیح بدی چرا nlognنیست؟

logn زمانی ساخته میشه که همچین چیزی داشته باشیم

for(i=1;i<=n;i=(i*2))

یا

for(i=n;i>1;i=(i/2))

نه مثل کد بالا که i یکی یکی اضافه میشه
همون طور که گفتم مشکلم در مورد for سومی که آیا 13 با تکرارش
در ضریب مخفی تاثیر داره یا نه؟

[whitehat]

سوالم اینه که for سومی در ضریب مخفی تاثیر داره یا نه؟

می خواهید چی را بدست بیاورید؟ اگه O هست جواب سوال منفی هست ولی اگه تتا باشه تاثیر داره

[mahdi bg]

سلام
منظورم دقیقا تتا بود می خواستم بدونم در محاسبه تتا باید 13 رو تاثیر
بدم یا اینه که تمام اون قسمت ها رو با تتا برابر یک حل کنم
ممنون

[rezvan_DP]

بله حق با شماست:

  ∑(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)

  

  

در نتیجه میتوان گفت که حلقه سوم در محاسبه تتا اثرگذار است.

[404_3140]

این حلقه که فقط داره تعداد عملیات رو در ضریب ثابتی ضرب می کنه...با توجه به تعریف این تابع همه چیش(!) همون n^2 می شه.
یعنی هم O هم omega هم teta (البته از نوع capital ش)