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) 

رسم درخت هم که سادست منتها نمیدونم چه جوری اینجا رسمش کنم.