Độ phức tạp thời gian (lớn O) của SortArrayUsingComparator là gì? iOS/OSX

Question

Tôi cần biết độ phức tạp về thời gian của các chức năng được sắp xếpArrayUsingComparator của lớp NSArray. Một nguồn sẽ là tuyệt vời kể từ khi tôi có khả năng đề cập đến nó trong luận án cử nhân của tôi. Tôi sắp xếp một mảng các vị trí theo khoảng cách đến vị trí hiện tại.

Câu trả lời duy nhất mà tôi có thể tìm được một ai đó nói rằng đó là ít nhất T (n) = O (n) nhưng nhiều khả năng T (n) = O (n log n)

Làm thế nào tôi có thể biết chắc chắn?

Answer 1

Bởi thử nghiệm thực tế của NSArray phân loại thời gian là phù hợp với O(n*log(n)).

Xem blog post

Lưu ý rằng trong một chú thích có một cách sắp xếp (PS9110) là O (n) nhưng là độc quyền và bằng sáng chế. Phương pháp này khá thú vị.

Answer 2

Thuật toán sắp xếp dựa trên chi phí so sánh ít nhất O (n log n). Xem này link

Vì tên của nó là sortedArrayUsingComparator cho thấy, phương pháp này dựa trên so sánh, vì vậy chi phí sẽ ít nhất là O (n log n).

Answer 3

Vâng để sắp xếp một mảng bạn phải xem ít nhất mọi phần tử chắc chắn là O(n). Có một số bài báo toán học cho bạn thấy rằng không thể có một thuật toán phân loại tốt hơn sau đó O(n*log(n)) như Mergesort chẳng hạn. Kể từ khi so sánh thực hiện một Mergesort Tôi nghĩ rằng sự phức tạp nên được O(n*log(n)) cho trường hợp tốt nhất, trung bình và tồi tệ nhất.

Bạn có thể tìm thấy một số thông tin về Mergesort đây: Mergesort

Và một số bài viết liên quan đến thời gian phức tạp thuật toán sắp xếp tốt nhất:

tôi không thể tìm thấy việc thực hiện chính xác của phương pháp đưa ra nhưng đây là bài viết tuyệt vời về cách bạn có thể đào sâu hơn trong việc triển khai Mảng trong Mục tiêu-C và để xem xét triển khai phương pháp: Exposing NSMutableArray