Nhấn vào đây để đọc bằng ngôn ngữ khác: English
Sức mạnh của một số cho biết phải sử dụng số đó bao nhiêu lần trong một phép nhân.
Nó được viết dưới dạng một số nhỏ bên phải và phía trên số cơ bản.
Làm thế nào để tính a mũ b?
Chúng ta nhân a cho chính nó, b lần. Tức là, a^b = a * a * a * ... * a (b lần của a).
Phép tính này sẽ mất O(n) thời gian vì chúng ta cần thực hiện phép nhân chính xác n lần.
Liệu chúng ta có thể làm tốt hơn so với thuật toán ngây thơ không? Có, chúng ta có thể giải quyết bài toán lũy thừa trong thời gian O(log(n)).
Thuật toán sử dụng phương pháp chia để trị để tính lũy thừa. Hiện tại, thuật toán này hoạt động cho hai số nguyên dương X và Y.
Ý tưởng đằng sau thuật toán dựa trên sự thật rằng:
Đối với Y chẵn:
X^Y = X^(Y/2) * X^(Y/2)
Đối với Y lẻ:
X^Y = X^(Y//2) * X^(Y//2) * X
trong đó Y//2 là kết quả của phép chia của Y cho 2 mà không có phần dư.
Ví dụ
2^4 = (2 * 2) * (2 * 2) = (2^2) * (2^2)
2^5 = (2 * 2) * (2 * 2) * 2 = (2^2) * (2^2) * (2)
Bây giờ, vì ở mỗi bước chúng ta cần tính lũy thừa X^(Y/2) giống nhau hai lần, chúng ta có thể tối ưu hóa nó bằng cách lưu trữ vào một biến trung gian để tránh tính toán trùng lặp.
Độ phức tạp thời gian
Vì mỗi lần lặp chúng ta chia mũ cho hai, sau đó chúng ta sẽ gọi hàm đệ quy log(n) lần. Do đó, độ phức tạp thời gian của thuật toán được giảm xuống thành:
O(log(n))