نیاز فوری به راهنمایی در مورد مرتبه‌ی اجرایی یک الگوریتم

[DumanNazeri]

سلام. وقت بخیر. خسته نباشید.
ببخشید من یه سوالی داشتم..
مرتبه‌ی اجرایی یک الگوریتم رو می‌خواستم پیدا کنم.. اما با چیزهایی که تا الآن دیدم فرق می‌کنه!


for i = 1 to n do
for j = 1 to [i/2] do
x = x +1;


فقط نکته این‌که جزء صحیح نیست. بلکه مقدار کف i/2 مد نظر هست..

بی‌نهایت ممنونم از لطف تون.

[rahnema1]

سلام
فرمول گاوس برای مجموع اعداد 1 تا n را در نظر بگیرید
اما در اینجا به جای n عدد n/2 هست و هر کدام از اعداد 2 بار تکرار میشن
نکته دیگه اینه که برای n که زوج یا فرد باشه دو عدد مختلف به دست میاد

zoj:
K = (n/2 - 1)
order = 2 * K * (K + 1)/2 + n/2
= 2* (n/2 - 1) * ((n/2 - 1)+ 1) /2 + n/2
= (n^2) / 4
fard:
K = ((n-1)/2)
order = 2 * K * (K + 1) / 2
= 2 * ((n-1)/2) * (((n-1)/2) + 1) / 2
= ((n^2)-1)/4

[DumanNazeri]

سلام
فرمول گاوس برای مجموع اعداد 1 تا n را در نظر بگیرید
اما در اینجا به جای n عدد n/2 هست و هر کدام از اعداد 2 بار تکرار میشن
نکته دیگه اینه که برای n که زوج یا فرد باشه دو عدد مختلف به دست میاد

zoj:
K = (n/2 - 1)
order = 2 * K * (K + 1)/2 + n/2
= 2* (n/2 - 1) * ((n/2 - 1)+ 1) /2 + n/2
= (n^2) / 4
fard:
K = ((n-1)/2)
order = 2 * K * (K + 1) / 2
= 2 * ((n-1)/2) * (((n-1)/2) + 1) / 2
= ((n^2)-1)/4


سلام قربان، بی‌نهایت ممنونم از لطف شما. مرسی.
پس n چه زوج باشه چه فرد مرتبه اجرایی این برنامه
O(n^2)
خواهد بود دیگه؟!

[rahnema1]

سلام قربان، بی‌نهایت ممنونم از لطف شما. مرسی.
پس n چه زوج باشه چه فرد مرتبه اجرایی این برنامه
O(n^2)
خواهد بود دیگه؟!

زوج:

O((n^2) / 4)

فرد:

O(((n^2)-1) / 4)