Phân loại chuỗi bằng cách sử dụng Hợp nhất Sắp xếp

Question

Độ phức tạp tồi tệ nhất để phân loại n chuỗi có n ký tự là gì? Nó sẽ chỉ là n lần mức trung bình của nó. trường hợp O(n log n) hoặc cái gì khác ...?

Answer 1

Khi @orangeoctopus, sử dụng thuật toán xếp hạng chuẩn trên bộ sưu tập của n chuỗi có kích thước n sẽ dẫn đến tính toán O(n^2 * logn).

Tuy nhiên - lưu ý rằng bạn có thể làm điều đó trong O(n^2), với các biến thể trên radix sort.

Cách đơn giản nhất để làm điều đó [theo ý kiến ​​của tôi] - là

1. xây dựng một trie, và cư nó với tất cả các chuỗi của bạn. Nhập mỗi chuỗi là O(n) và bạn làm điều đó n lần - tổng số O(n^2)
2. làm DFS trên trie, mỗi lần bạn gặp dấu chấm hết cho chuỗi - thêm nó vào bộ sưu tập được sắp xếp. Thứ tự của các chuỗi được thêm vào theo cách này là từ điển, do đó danh sách của bạn sẽ được sắp xếp theo từ điển khi bạn hoàn thành.

Nó rất dễ dàng để xem bạn không thể làm điều đó tốt hơn bất kỳ sau đó O(n^2), vì chỉ đọc dữ liệu là O(n^2), do đó giải pháp này là tối ưu về mặt ký hiệu O lớn thời gian phức tạp.

Answer 2

Khi bạn đang nói về O ký hiệu với hai thứ có độ dài khác nhau, thông thường bạn muốn sử dụng các biến khác nhau, như M và N.

Vì vậy, nếu loại hợp nhất của bạn là O(N log N), nơi N là số chuỗi ... và so sánh hai chuỗi là O(M) nơi M quy mô với chiều dài của chuỗi, sau đó bạn sẽ được trái với:

O(N log N) * O(M) 

hoặc

O(M N log N) 

nơi M là chiều dài chuỗi và N là số chuỗi. Bạn muốn sử dụng các nhãn khác nhau vì chúng không có nghĩa giống nhau.

Trong trường hợp kỳ lạ nơi chiều dài chuỗi trung bình tỉ lệ với số chuỗi, như thế nào nếu bạn đã có một ma trận lưu trữ trong chuỗi hoặc một cái gì đó như thế, bạn có thể tranh luận rằng M = N, và sau đó bạn sẽ phải O(N^2 log N)

Answer 3

Sắp xếp mục n với MergeSort yêu cầu số O(N LogN) so sánh. Nếu thời gian so sánh hai mục là O(1) thì tổng thời gian chạy sẽ là O(N logN). Tuy nhiên, so sánh hai chuỗi độ dài N yêu cầu O(N) thời gian, do đó, việc triển khai ngây thơ có thể bị kẹt với thời gian O(N*N logN).

Điều này có vẻ lãng phí vì chúng tôi không tận dụng lợi thế của thực tế là chỉ có N chuỗi xung quanh để so sánh. Chúng ta bằng cách nào đó có thể xử lý trước các chuỗi để so sánh mất ít thời gian hơn trung bình.

Đây là một ý tưởng. Tạo một cấu trúc Trie và đặt N chuỗi ở đó. Trie sẽ có O(N*N) nút và yêu cầu O(N*N) thời gian để xây dựng. Traverse cây và đặt một số nguyên "xếp hạng" cho mỗi nút tại cây; Nếu R (N1) < R (N2) thì chuỗi liên kết với Node1 xuất hiện trước chuỗi được liên kết với Node2 trong từ điển.

Bây giờ, hãy tiếp tục với Mergesort, thực hiện so sánh trong O(1) thời gian bằng cách tra cứu Trie. Tổng thời gian chạy sẽ là O(N*N + N*logN) = O(N*N)

Chỉnh sửa: Câu trả lời của tôi rất giống với @amit. Tuy nhiên tôi tiến hành với mergesort, nơi ông tiến hành với radixsort sau khi bước xây dựng trie.