Gần đây, tôi đã gặp phải sự cố C++. Đây rồi.Sắp xếp một mảng với các phần tử khác nhau, từ 0 đến 9999
Giả sử bạn biết rằng tất cả các giá trị trong một mảng số nguyên rơi vào phạm vi từ 0 đến 9999. Chứng minh rằng người ta có thể viết một O (N) thuật toán để sắp xếp mảng với hạn chế này
Để hiểu biết của tôi một thuật toán của O (N) là một trong những nơi bạn đi qua một bộ nhất định của O (1) hoạt động N lần. Bây giờ cho cuộc sống của tôi, tôi không thể hiểu làm thế nào bạn sẽ đi về viết một chương trình mà sắp xếp một loạt các con số liên quan đến O (N). Sắp xếp theo dạng cơ bản nhất của nó bao gồm so sánh các số với nhau và không có thuật toán để làm điều đó trong một lần lặp và kết thúc với một mảng được sắp xếp.
Trong câu hỏi, nó làm cho điểm mà một phần tử của mảng này chỉ có thể có giá trị trong phạm vi 0-9999. Tôi có thể hiểu được từ câu hỏi rằng hạn chế này là những gì làm cho toàn bộ điều có thể và tôi nên sử dụng nó trong thuật toán của tôi để đạt được một giải pháp. Nhưng tôi vẫn không đi đâu cả. Tất cả các thuật toán sắp xếp mà tôi biết (Chọn, Chèn, Hợp nhất, Nhanh ...) tất cả đều có thời gian chạy lớn hơn O (N) với tối thiểu là O (log N).
Tôi có thể hiểu rằng một số thuật toán có thể có thời gian chạy của O (N), nhưng chỉ trong trường hợp tốt nhất của chúng. Nhưng tôi không nghĩ câu hỏi đang được hỏi về khía cạnh đó.
Nếu bất kỳ ai cũng có thể tiết lộ bất kỳ thông tin chi tiết nào về vấn đề này, tôi sẽ đánh giá cao nó.
+1 cho "Chỉ loại so sánh là O (n log n)" – xtofl
+1 để sử dụng đúng "Omega" thay vì "O". –
@xtofl: Cảm ơn :) Tôi nên chỉ ra rằng mặc dù Omega (n lg n) và O (n lg n) không phải là điều tương tự - đầu tiên là một ràng buộc thấp hơn, trong khi thứ hai là một ràng buộc trên. Vấn đề là các loại so sánh là * ít nhất * linearithmic trong n. Để đánh bại n lg n, bạn phải sắp xếp theo một cách khác. –