پیچیدگی الگوریتمی

[Nima NT]

با عرض سلام و وقت به خیر.
بنده کدی دارم به شرح زیر...


int f(int n){
if(n<=1)
return 1;
else
return f(n/2) + n/2;
}
یک از دوستانم به بنده میگفت که پیچیدگی این الگوریتم nlogn هست ولی بنده دقیقا" نفهمیدم چرا ، ممنون میشم اگر کمکم کنید.:ناراحت:
آیا اصلا" پاسخی که داده درست هست ؟

[qwerty11]

سلام،

خوب به خاطر اینکه دوستت اشتباه گفته نفهمیدی دیگه :لبخند:

پیچیدگیش log n هستش. T(n)=T(n/2) I . خوب اگر این معادله رو حل کنی، T(n) I جوابش log n میشه. (I هایی که گذاشتم رو ندید بگیر).