Mà cái độ phức tạp này ý nghĩa thực tế thế nào nhỉ, nhìn nó rất Toán, không biết có tính được ra tốc độ chạy code không
[Chia để trị] Tính lũy thừa a^n
Theo em hiểu sơ sơ (không học nhưng cũng lướt lướt) thì cái đó tính thời gian chạy của thuật toán (ví dụ cho i lặp từ 1 đến n, mỗi lần lặp là 1 bước, n lần lặp là n bước), space (gọi thế nào cho chuẩn nhỉ, chắc là khoảng tài nguyên sử dụng), rồi còn 1 cái nữa là gì ấy em không biết.
Và theo em nhìn qua thì đúng là nó
1 Like
tính độ phức tạp này đâu có gì khó đâu 
mà “độ phức tạp” với “tốc độ chạy code” (thời gian) là khác nhau 
2 Likes
Thể nó tính được gì ạ ?
Có lẽ là số bước ?
20 char
Log hay lẻ lắm, số bước thì chắc phải nguyên chứ nhỉ 
Em đang viết bài về vụ này, có lẽ trong nay mai sẽ được thôi. Cái này rắc rối quá, đọc đi đọc lại nãy giờ. Giờ phải viết làm sao cho người ta hiểu.
1 Like
A, anh tìm được tài liệu tiếng việt rồi, nhưng cái này phải biết giới hạn (lim: 1 khái niệm toán nhá, lớp 12 học),
Em đang làm bài về Asymptotic Notation (tiệm cận), không biết nó có liên quan đến độ phức tạp (complexity không)
Cái này mang tính học thuật quá. Nói chung là ước lượng thời gian chạy: O lớn, o nhỏ, Omega… nói chung là để tính thời gian chạy trong TH tốt, xấu, trung bình…
1 Like
Thực ra là làm tròn lên, nhưng khi làm tròn nó chỉ dc cộng 1 số 0<=c< 1 nên bị bỏ qua.
1 Like
@Gio
@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 
Em có cuốn đó rồi anh, cám ơn anh. 
chắc chút nữa bài viết về vụ này sẽ xong
1 Like
Kinh nhờ? Ôi lạc hậu mất thôi 
2 Likes
Là sao hả bạn ?
20 char
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
(n & 1) có nghĩa là gì vậy bác?
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
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)
Đị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 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
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
Sẽ đúng nếu cho n đủ lớn và thuật toán chỉ chạy trên RAM.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?