Thống kê thứ tự thứ i trong Python

Question

Đưa ra danh sách các thành phần có thể so sánh (số hoặc chuỗi), thuật toán tối ưu để tìm phần tử thứ tự i có thời gian là O(n).

Python có thực hiện thống kê O(n) thống kê thứ tự thời gian cho danh sách, dấu trang, bộ, ... không?

Answer 1

Không có cấu trúc dữ liệu được đề cập nào của Python thực hiện nguyên tắc thuật toán thống kê thứ tự thứ tự.

Thực tế, nó có thể không có ý nghĩa nhiều đối với từ điển và bộ, vì thực tế là cả hai không đưa ra giả định về thứ tự các phần tử của nó. Đối với các danh sách, sẽ không khó để triển khai selection algorithm, cung cấp thời gian chạy O (n).

Answer 2

Nếu tôi < < n bạn có thể cho một cái nhìn tại http://docs.python.org/library/heapq.html#heapq.nlargest và http://docs.python.org/library/heapq.html#heapq.nsmallest (những không giải quyết được vấn đề của bạn, nhưng nhanh hơn so với phân loại và lấy phần tử thứ i).

Answer 3

Đây không phải là giải pháp gốc, nhưng bạn có thể sử dụng số partition của NumPy để tìm số k thứ tự thống kê của danh sách trong thời gian O (n).

import numpy as np 
x = [2, 4, 0, 3, 1] 
k = 2 
print('The k-th order statistic is:', np.partition(np.asarray(x), k)[k]) 

EDIT: điều này giả định zero-lập chỉ mục, ví dụ: các "số liệu thống kê theo thứ tự 0" ở trên là 0.