tính độ phức tạp của thuật toán

[mr tũ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;
}

giải thuật như trên và đề là tính thời big O.
Các bạn nêu rõ trường hợp nào bao nhiêu phép toán với thời gian là gì giúp mình nhé.

View more random threads:

• [Thắc mắc] Khi sử dụng kiểu string của C++ trong Studio 2013
• Cần giúp đỡ bài tập vẽ chữ số điện tử
• copy noi dung tu stack S sang stack D
• Tùy biến lệnh cout
• găp lỗi như hình vẽ về opencv
• Em mới học C, bài tập mảng một chiều
• Khi nào sử dụng con trỏ !!
• Hỏi về struct
• NHân 2 ma trận trên C, giúp sửa lỗi bài này!!!
• [C]Bài tập tính đa thức - cần giúp đỡ

[heartless]

nếu mình nhớ không nhầm thì độ phức tạp là gồm:
phép gán
phép so sánh
các phép toán + - * / ...
còn gì nữa không nhỉ

[viet1234]

Bài này giống như lũy thừa mod. (nếu cần chứng minh đầy đủ thì mình chịu)

Nếu lũy thừa mod thì O(logn), còn lũy thừa lên hoài luôn thì O(logn)*O(log^2n)=O(log^3n).