Giải thích cách tư duy Divide and Conquer được ứng dụng trong thuật toán lũy thừa nhanh (Binary Exponentiation) để tính a^n với độ phức tạp O(log n)?

Question

Accepted Answer

Thay vì nhân a liên tiếp n lần (độ phức tạp O(n)), ta chia bài toán thành: nếu n chẵn, a^n = (a^(n/2))^2; nếu n lẻ, a^n = a * (a^((n-1)/2))^2. Việc chia đôi số mũ ở mỗi bước giúp giảm số lượng phép nhân theo hàm logarit. Đây là kỹ thuật nền tảng trong các thư viện mật mã học (Cryptography) để xử lý các số nguyên cực lớn.

Giải thích cách tư duy Divide and Conquer được ứng dụng trong thuật toán lũy thừa nhanh (Binary Exponentiation) để tính a^n với độ phức tạp O(log n)?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi divide & conquer liên quan cùng chủ đề