Tôi đã tự hỏi về độ phức tạp của shuffle function trong thư viện/mô-đun Python random. Có phải O (n) hay ít hơn?hiệu suất thuật toán python shuffle
Có một trang web hiển thị thời gian phức tạp của các hàm thuộc về thư viện Python không?
Bạn không thể phát ngẫu nhiên danh sách theo cách hoàn toàn ngẫu nhiên trong ít hơn O (n).
implementation of random.shuffle() sử dụng Fisher-Yates shuffle algorithm, dễ thấy là O (n).
Cảm ơn bạn! Tôi đoán tôi cần chức năng ngẫu nhiên của riêng tôi (không hoàn toàn ngẫu nhiên tôi đoán) –
@Saher: bạn thậm chí có thể quan niệm của một phương pháp xáo trộn một danh sách tại chỗ đó là tốt hơn so với O (n)? – geoffspear
Tôi đã không nghĩ rằng thông qua nhưng những gì tôi có nghĩa là về cơ bản cho mục đích của tôi cho các thuật toán tôi đang viết tôi chỉ có thể shuffle đầu tiên 4-5 mục và chọn đầu tiên, nó không phải là rất quan trọng. –
Đối với câu hỏi thứ hai của bạn - http://wiki.python.org/moin/TimeComplexity –
@Alex: xem xét thư viện duy nhất trong danh sách đó là 'bộ sưu tập', chứ không phải những gì OP yêu cầu, tôi nghĩ vậy. – geoffspear
@Wooble Đó là một wiki, do đó, nó có thể không bị giới hạn chỉ là 'bộ sưu tập' trong tương lai. (Khi đọc lại, có vẻ như đây là đối với CPython, nhưng ít nhất là một tài liệu tham khảo thú vị. Nó có thể truyền cảm hứng cho ai đó tạo một trang wiki tương đương cho 'ngẫu nhiên' và các thư viện khác) –