به نام خدا
سلام
رفقا دو تا سوال داشتم:
۱- T(n) = T(n-2) +lgn جوابش چی می شه؟ من دیدم نوشته بود nlgn اما چرا؟
۲- اگر پیچیدگی الگوریتمی به صورت N^2+ N^2+N^2 ... باشه آیا جواب می شه theta(n^3 یا می شه Theta(n^2 ؟
به نظرم میشه اینجوری حلشون کرد
در مورد سوال اولتتون دنباله‌ی حاصله به این شکل میشه
[tex]Lgn lg(n-2) lg(n-4) ...=lg(n(n-2)(n-4)...)\approx lg(n^{n})=nlgn[/tex]
در مورد سوال ۲ اگه تعداد تکرار این N^2ها N تا باشه N^3 میشه
[tex]n^2 n^2 ...=n^2(1 1 1 ...)=n^2(n)=n^3[/tex]