我的程序監聽輸入數據，並且每秒鐘估計有5個數據。所有的數據將被存儲在一個數據結構中。當數據結構大小爲360 000時，我需要在存儲的數據中找到第25，第50和第75百分位數。大小爲360 000的數據結構的第25，第50和第75百分位
以下哪一項更有效？或者，如果你知道一個更好的方法，請幫助我。
我應該使用訂單統計樹嗎？ 插入，刪除（log n）。或者我應該等到它已經收集了所有360 000個數據，然後對其進行分類並從中找到第25，第50和第75百分位數。
您可以使用選擇排序來查找不同的百分位數。
在你的問題你知道你需要找到排序列表中的90k，180k和270k定位元素。 一旦獲取了所有360k元素，選擇一個隨機元素並根據比您選擇的元素更小，等於和大的元素將元素拆分爲子列表。 完成該步驟後，您將能夠看到您選擇的元素在哪個位置。然後，您可以選擇對較小或較大的子列表執行相同操作，具體取決於您要查找的百分位數。
在最好的情況下，這可以在O（n）中解決，因爲你可以在第一時間選擇正確的百分位，但這是不太可能的。 在最壞的情況下，你總是可以選擇最小的元素，因此確實通過o（n）次使它成爲o（n^2），但那不太可能。 幸運的是，預期的運行時間結果是T（n）< = 8n，這是線性運行時間。
作爲提示，您可以在數據流式傳輸過程中收集最小/最大數字，然後可以通過選擇第一個元素進行估算（最大+最小）/ 2。這當然是一個假設，即數字在某種程度上類似於正態分佈，而不是完全關閉。
如果您需要在算法的細節，看看這裏：http://cseweb.ucsd.edu/~dasgupta/103/4a.pdf
5次/秒，意味着你有一個整體的200ms來處理每一個事件，這是年齡。有了這些限制，您可以在內存中保留一個排序的統計樹。 – radai
這裏是捕捉。在這些事件中，還有其他正在對輸入數據執行的操作。我想知道使用這棵樹是否更昂貴，因爲數據大小趨於360 000會減慢。或者等到它填滿後再分類？ – jerr
確實取決於您的延遲要求。如果你不介意額外的幾秒鐘，它將在最後對整個事物進行排序，而不是最好的方法。 – radai