設計一種算法，對O中的序列進行排序（nloglogn）

Question

輸入是一個有n個整數的序列，有許多重複，這樣序列中不同整數的個數爲O（log n）。設計排序算法（僅基於比較）在最差情況下使用至多O（n log log n）比較來排序此類序列。

有人可以解釋爲什麼我應該使用紅黑樹而不是合併排序或其他排序算法。另外我怎樣才能計算大o成爲n日誌日誌n。

Answer 1

，因爲使用的是紅黑樹你有這棵樹的log（n）的插入，你將有隻有不同的元素，並保持每個元素 的數量，使得你的log（n）僅元素及其計數。 排序你需要插入n個元素到最大尺寸應該是log（n）的樹中，所以你需要nlog（log（n））作爲整個事物，當你有樹時，你可以簡單地按照排序順序遍歷它並重復每個元素k次，其中k是元素數量。