Độ phức tạp của trường hợp tốt nhất/xấu nhất/trung bình (trong ký hiệu Big-O) của cấu trúc dữ liệu trie để chèn và tìm kiếm là gì?Thời gian chạy tốt nhất/tồi tệ nhất/trung bình Big-O của cấu trúc dữ liệu Trie là gì?
Tôi nghĩ rằng đó là O(K) cho tất cả các trường hợp, trong đó K là độ dài của chuỗi tùy ý đang được chèn hoặc tìm kiếm. Ai đó sẽ xác nhận điều này?
Theo Wikipedia và this source, sự phức tạp trường hợp xấu nhất để chèn và tìm kiếm một Trie là O(M) nơi M là chiều dài của một phím. Tôi không tìm thấy bất kỳ nguồn nào mô tả sự phức tạp tốt nhất hoặc trung bình của việc chèn và tìm kiếm. Tuy nhiên, chúng ta có thể nói rằng độ phức tạp của trường hợp tốt nhất và trung bình là O(M) trong đó M là độ dài của khóa, vì Big-O chỉ mô tả giới hạn trên về độ phức tạp.
Có một số thông tin tuyệt vời về điều này trên Wikpedia. http://en.wikipedia.org/wiki/Trie
k: độ dài của chuỗi mà bạn tìm kiếm hoặc chèn.
For Search
Worst: O(26*k) = O(k)
Average: O(k) # In this case, k is an average length of the string
Best: O(1) # Your string is just 'a'.
Độ phức tạp của Trie không thay đổi với số chuỗi bạn tìm kiếm, chỉ với độ dài của chuỗi tìm kiếm. Đó là lý do tại sao Trie được sử dụng khi số lượng chuỗi tìm kiếm lớn, như tìm kiếm toàn bộ từ vựng trong từ điển tiếng Anh.
For Insertion
Worst: O(26*k) = O(k)
Average: O(k)
Best: O(1)
Vì vậy, có, bạn nói đúng. Có thể bạn đã thấy O (MN) và điều đó có thể làm bạn bối rối nhưng nó đơn giản chỉ nói về khi bạn cần làm trên O (k) hoạt động N lần.