[Chia để trị] Tính lũy thừa a^n

#21

@Gio :+1:
@nhatlonggunz Em xem tài liệu này xem, có nói chi tiết về tính dpt đấy, có cả phương pháp chia để trị luôn :smiley:

http://download.tlvnimg.com//520444db935e8a3a04520323cb55c15b/55422750/source/2011/20111203/conngaygaplai/thiet_ke_va_danh_gia_thuat_toan_9853.pdf

#22

Em có cuốn đó rồi anh, cám ơn anh. :slight_smile: chắc chút nữa bài viết về vụ này sẽ xong

1 Like
#23

Kinh nhờ? Ôi lạc hậu mất thôi :sunny:

2 Likes
#25

Là sao hả bạn ?

20 char

#26

nói về tính toán độ phức tạp của bài toán, người ta phân tích một thuật toán có tối ưu hay không (nhanh hay chậm) là dựa vào độ phức tạp của nó. ví dụ thuật toán tính lũy thừa theo phương pháp ngây thơ sẽ mất thời gian O(n) nghĩa là tính lũy thừa mất n phép tính ví dụ n=2^30=1073741824 phép tính, nhưng sử dụng chia để trị thì thời gian tính giảm xuống còn O(log n) (logarit cơ số 2 của n) tức là mất khoảng log(2^30) bằng 30 phép tính => giảm đc số lượng phép tính khổng lồ tương đương với rút ngắn thời gian tính toán, thuật toán sẽ trở nên tối ưu hơn. độ phức tạp của thuật toán được qui về giá trị mũ lớn nhất của đa thức tổng phép tính, ví dụ phân tích một thuật toán cho số lượng phép toán là 3.n^3+n+1 thì độ phức tạp của nó sẽ là O(n^3), thế nên không thể nói độ phức tạp là số lượng phép tính chính xác mà chỉ là giá trị để đánh giá độ tối ưu của thuật toán

2 Likes
#27

(n & 1) có nghĩa là gì vậy bác?

#28

n & 1 là phép and trên bit, n & 1 trả về n % 2
Trong trường hợp kia thì nếu n lẻ thì return tmp * tmp * a, nếu không thì return tmp * tmp

2 Likes
#29

Với input đủ lớn thì có thể thấy được rõ rệt: gấp đôi thì thời gian chạy tăng 4 lần, vậy gấp 1.5 lần thì… chịu khó đo thời gian rồi vẽ đồ thị từ từ sẽ nhìn ra.

Thực ra phải là lim sup với lim inf mới đúng vì sin(n) không có lim nhưng vẫn là O(1) :slight_smile:
Định nghĩa của mấy kí hiệu đó ban đầu không được phát biểu dưới dạng lim do đang làm toán rời rạc :smiley: nếu chỉ dùng giới hạn bt thì khá căng cho 1 số hàm. Dùng ngay định nghĩa rời rạc thì sin(n) vẫn là O(1) vì có quá 1 được đâu :slight_smile:

Cái lợi khi sử dụng định nghĩa với giới hạn là bạn có thể hiểu những câu ntn: sin(x) = x + O(x^3) vậy lim(x->0)(sin(x)/x) = lim(x->0) ((x + O(x^3))/x) = 1 (câu này là ví dụ thôi nhé vì Taylor-Maclaurin phải có đạo hàm, mà đạo hàm sin suy từ lim của sinx/x)

1 Like
#30

Sẽ đúng nếu cho n đủ lớn và thuật toán chỉ chạy trên RAM.

#31

a, n là số thực??! :smiley:

#32

Dùng a^n = e^(n*ln a)

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?