Tăng tốc bài toán tính tổng các của n (trừ n)

#21

Sai :slight_smile: còn nhanh hơn là khác.

  • Nếu là số nguyên tố thì bạn chia tới căn n là xong, như nhau.
  • Nếu là hợp số dạng pq thì bạn sẽ chia tới căn q thay vì căn pq (nhanh hơn).
  • Nói chung càng nhiều thừa số thì càng nhanh, do số bị chia giảm qua mỗi thừa số tìm được.

Tức là cận trên ban đầu là căn(n), sau mỗi thừa số tìm được ta tính lại cận (nhỏ hơn), vì vậy nhanh hơn.

1 Like
#22

Bạn có thể tính độ phức tạp của cả sàng, phân tích, và tính giùm mình được không ?

#23

Phần này bạn lập topic mới nhé.

1 Like
#24

Mình vẫn đang nói về tăng tốc bài toán tính tổng ước của topic này mà, sao lại lập topic khac.

#25

Vậy thì sàng để topic khác vậy.

Với cách chia thử thì ai cũng biết tối đa là O(sqrt(n)) phép mod, nhưng trung bình thì bao giờ nó cũng khó tính cực kì. https://cs.stackexchange.com/questions/50326/what-is-the-average-case-complexity-of-trial-division (kết quả là theta(sqrt(n)/log(n)).

Sách Prime Numbers: A Computational Perspective trang 120 có đưa ra một ước lượng khác nhưng không thuyết phục lắm.

1 Like
#26

Thuật toán của mình mình sẽ chạy O(sqrt(N))
Nhưng mình đang hỏi tổng độ phức tạp thuật toán của bạn mà.

#27

Thực ra thuật toán của bạn sẽ cần [sqrt(n)] - 1 phép mod trong mọi trường hợp.

Phân tích TSNT theo kiểu chia thử sẽ có độ phức tạp phụ thuộc vào căn bậc hai của thừa số nguyên tố lớn nhất (là n nếu n nguyên tố). Nếu tính trung bình thì sẽ là theta(sqrt(n)/logn) phép mod. http://www.sciencedirect.com/science/article/pii/0022404993900939

1 Like
#28

Mình hiểu rồi, cám ơn bạn <3

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