3 سوال مربوط به ساختمان داده

[haricanboy]

سلام دوستان
2 تا سوال مربوط به ساختمان داده دارم راه حل و جوابش رو میخوام پیدا کنم چطوری حل میشن

1- مرتبه اجرایی الگوریتم زیر را حساب نمایید.


For j=1 to m do
For k=1 to j do
X=x+1

---------------------------------------------------------
2- با در نظر گرفتن ضابطه مقابل تعداد عمل جمع برای N=8 را محاسبه نمایید.(راهنمایی درخت مربوطه را ترسیم نمایید).


int T(int n){
if(n<=1){
return 1;
else
return( T(n/2) + T(n/2));
}
}

------------------------------------------------------
ممنون

[haricanboy]

کسی پاسخگو نیست؟
مهمه ها

[soorena]

سلام
شاید چون سوال درسی هست کسی پاسخ نمیده یا شایدم کسی حوصله تایپ کردن نداره...
ج سوال 1 :
مرتبه اجرایی الگوریتم همون تعداد دفعات اجرای خط سوم هستش.

1+2+3+4+...+(n-1)+n=n(n+1)/2

سوال دو :
در مورد رابطه بازگشتی داریم :

T(n)=2T(n/2)+1
و طبق قضیه مستر داریم :

a=2,b=2,f(n)=O(1) -> nlogba=n -> T(n)=theta(n)
رسم درخت هم که سادست منتها نمیدونم چه جوری اینجا رسمش کنم.