Giúp giải bài tập tìm độ phức tạp của thuật toán đệ quy

[Duong_van_Hoa]

xét thuật toán tính f(x,n)=x^n :
int F(int x, int n)
{
if(n==0)
return 1;
else if (n%2==0)
return F(x,n/2)*F(x,n/2);
else return F(x,n/2)*F(x,n/2)*x;
}
Gọi T(n) là thời gian tính của thuật toán.
a) xây dựng công thức đệ quy cho T(n)
b) giải công thức đệ quy để đưa ra đánh giá cho T(n)

[rogp10]

Bạn cho vào thẻ code để không bị mất kí hiệu

Lập công thức truy hồi, sau đó khai triển dần dần ra xem nó là ntn, rồi chứng minh.

[hell6w9rld (HelloWorld)]

câu a thì lập công thức truy hồi ( công thức đệ quy)
còn câu b, nếu giải công thức truy hồi ( đệ quy ) thì chỉ tìm ra được 1 công thức khác, mà thay x với n vào đó, ta tìm ngay được giá trị của hàm f mà k cần phải làm theo trình tự của đệ quy, chứ nó k chỉ ra được độ phức tạp của thuật toán, mình nghĩ thế, muốn đánh giá độ phức tạp của thuật toán, thì áp dụng big 0 vào công thức đệ quy, thường thì mình thấy ng ta đánh giá độ phức tập thuật toán khi đã có code ( với ng lập trình ) còn với nhà khoa học máy tính, chuyên toán, thì đánh giá độ phực tạp từ ý tưởng thuật toán, như mình học ở trường mình chỉ được học mấy cái độ phức tập khi đã có code, còn phân tích từ góc độ toán học thì phải học mấy môn phân tích thiết kế thuật toán, toán rời rạc, cấu trúc dữ liệu giải thuật của mấy trường mà có khoa khoa học máy tính, hoặc có ngành cntt nhưng chuyên bộ môn khoa học máy tính ấy

[nguyenhuuca (Nguyen Ca)]

Không hiểu chỗ nào thì hỏi, không nhờ giải bài tập