là python bộ s.difference_update (t) O (m X n)

Question

Vấn đề tuyên bố:

tôi đang làm việc trên một vấn đề mà tôi có một cơ sở dữ liệu với một danh sách rất lớn của các tập tin từ hệ thống tập tin. Nếu một loạt tệp bị xóa khỏi hệ thống, cùng một tệp sẽ được cập nhật trong cơ sở dữ liệu.

Cách tiếp cận:

danh sách truy vấn của tập tin từ db và danh sách các tập tin từ hệ thống tập tin. Sau đó so sánh nếu mỗi tệp từ db nằm trong danh sách khác. Xóa nếu không tìm thấy Để tránh một tra cứu của mỗi tập tin từ danh sách liên tục, tôi đang lên kế hoạch để sử dụng bộ trong python và phương pháp difference_update()

Câu hỏi:

Bên trong, sẽ này một lần nữa có sự phức tạp của O (m X n), giống như cách tiếp cận khác của tìm kiếm lặp lại hay nó được tối ưu hóa để giảm độ phức tạp?

Answer 1

Nó sẽ là O(len(t)) như đã nêu trong nhận xét, do cài đặt liên tục tra cứu thời gian.
Cũng được xác nhận trong http://python-reference.readthedocs.org/en/latest/docs/sets/difference_update.html