Độ phức tạp tính toán của thuật toán Apriori có thể bị ảnh hưởng bởi các yếu tố sau:
Ngưỡng hỗ trợ - Giảm ngưỡng hỗ trợ dẫn đến các tập phổ biến cao hơn được thông báo là thường xuyên. Điều này có ảnh hưởng không thuận lợi đến độ phức tạp tính toán của thuật toán vì các tập phổ biến ứng viên cao hơn nên được tạo ra và tính.
Kích thước tối đa của các tập phổ biến cũng ảnh hưởng đến việc cải thiện với các ngưỡng hỗ trợ thấp hơn. Khi kích thước tối đa của các tập phổ biến được cải thiện, thuật toán sẽ được yêu cầu để tạo nhiều lần chuyển hơn trên tập dữ liệu.
Số lượng mặt hàng (Kích thước) - Khi số lượng một số vật phẩm tăng lên, sẽ cần nhiều dung lượng hơn để lưu số lượng vật phẩm hỗ trợ. Nếu nhiều mục thường xuyên cũng tăng theo kích thước của dữ liệu, thì giá trị tính toán và I / O sẽ tăng do số lượng tập mục ứng viên được tạo ra bởi thuật toán cao hơn.
Số lượng giao dịch - Do Apriori, thuật toán tạo ra các lần lặp lại qua tập dữ liệu, thời gian chạy của nó tăng lên với số lượng giao dịch cao hơn.
Chiều rộng giao dịch trung bình - Đối với các tập dữ liệu dày đặc, độ rộng giao dịch trung bình có thể cao. Điều này ảnh hưởng đến độ phức tạp của thuật toán Apriori theo hai phương pháp, chẳng hạn như kích thước tối đa của các tập phổ biến thường xuyên ảnh hưởng tăng lên khi chiều rộng giao dịch trung bình tăng lên. Chiều rộng giao dịch tăng lên, các tập hợp vật phẩm cao hơn được đưa vào giao dịch. Điều này sẽ làm tăng nhiều lần truyền qua cây băm được triển khai trong quá trình đếm hỗ trợ.
Tạo tập hợp l-itemset thường xuyên - Đối với mỗi giao dịch, phải cập nhật số lượng hỗ trợ cho từng mặt hàng có trong giao dịch. Xét rằng w là độ rộng giao dịch trung bình, hoạt động này cần thời gian O (Nw), trong đó N là tổng số giao dịch.
Thế hệ ứng viên - Nó có thể tạo ra các tập phổ biến k ứng cử viên, các cặp thường xuyên (k - 1) - các tập phổ biến được kết hợp để quyết định xem chúng có tối thiểu k - 2 mục chung hay không. Mỗi phép toán kết hợp cần tối đa k - 2 phép so sánh bằng nhau. Trong trường hợp tốt nhất, mỗi bước kết hợp tạo ra một k-itemet ứng viên khả thi.
Trong trường hợp xấu nhất, thuật toán nên kết hợp từng cặp tập thường xuyên (k - 1) -item được tìm thấy trong lần lặp trước. Do đó, chi phí hoàn chỉnh của việc hợp nhất các tập phổ biến thường xuyên là
$$ \ mathrm {\ displaystyle \ sum \ limit_ {k =2} ^ w \ :( k-2) | C_ {k} | <\:Cost \:of \:merge \:<\ displaystyle \ sum \ limit_ {k =2} ^ w \ :( k-2) | F_ {k} -1 | ^ 2} $$
Một cây băm cũng được tạo ra trong quá trình tạo ứng viên để lưu các tập phổ biến ứng viên. Do độ sâu tối đa của cây là k, chi phí để điền vào cây băm với các tập phổ biến ứng viên là O ($ \ mathrm {\ displaystyle \ sum \ limit_ {k =2} ^ w \:k | C_ {k} | } $).
Trong quá trình cắt bỏ ứng viên, cần phải kiểm tra xem k - 2 tập con của mỗi tập k mục ứng viên có thường xuyên hay không. Bởi vì chi phí để xem một ứng cử viên trong cây băm là O (k), bước cắt bỏ ứng viên cần O ($ \ mathrm {\ displaystyle \ sum \ limit_ {k =2} ^ w \:k | C_ {k} |} $) thời gian.