C++排序向量時間複雜度

Question

假設我有一個vector<vector<int>> L帶有N個向量，並且跨所有向量求和的總數最多爲M.什麼是標準C++排序sort(L.begin(), L.end())最嚴格的時間複雜度？

vector<int>比較函數的運行時間至多爲O（M），所以明顯的界限是O（NM log N）。但是如果我們實現標準的mergesort，我們可以看到在每個O（logN）級別中，最多進行O（M）個整數比較，因此運行時間爲O（（N + M）logN）。這是因爲比較兩個長度爲A和B的向量需要O（min（A，B））時間。

C++標準是否保證運行時爲O（（N + M）log N）？

Answer 1

沒有足夠的信息。您還需要知道N向量中的M值的分佈。如果你有，那麼它直截了當地發現總體複雜性：

1. std::sort擁有的O(N·log(N))比較複雜。

2. std::vector使用std::lexicographical_compare(v1, v2)進行比較，其複雜性爲O(min(v1.size(), v2.size()))比較。

3. int比較具有O(1)的複雜性。

4. 我們會通知E(M, N)是對M的函數，N，返回意味着數目的最小元素每一對內矢量之間。

   • 例如，如果你有一個均勻分佈，這是 平凡等於M/N。
5. 取產品： Big Oh = N·log(N)·E(M, N)·1。
   • 對於均勻分佈，這將是M·log(N)。

您可以使用Discrete Probability Distribution theory找出E(M, N)功能是什麼的M跨N任何分配。

---

編輯1：爲了推動如何/爲什麼這重要的一點：考慮分佈總是讓我向量的樣子：

outer[0].size() == 1, 
outer[1].size() == 1, 
outer[2].size() == 1, 
..., 
outer[M-1].size() == (M - N + 1) 

在這種情況下，E(M, N) = 1，因爲std::lexicographical_compare將只有一個一個其他元素與任何元素對進行比較。因此，對於這種特殊的分配，我會總是有一個複雜的O(N·log(N))。但有了統一的分配，我將有O(M·log(N))。

---

編輯2：按照你定義你的發行版的評論，讓我們嘗試並找到E(M, N)。

首先，請注意總共有T = (N choose 2) = N(N - 1)(1/2)矢量比較的不同組合。

一個（並且只有一個）的組合將採取X = O((M - N + 2)(1/2))比較，並且具有概率P(X) = 1/T發生。

每隔組合將需要的只是1比較（O(1)），並與概率P(1) = (T - 1)/T所以出現這些情況。

查找平均值很簡單：X·P(X) + 1·P(1)。

鑑於此，WolframAlpha說：E(M, N) = (M + (N - 2) N)/((N - 1) N)。

乘以該功能通過N log(N)給我們(M + (N - 2) N) log(N)/(N - 1)，這可以進一步簡化，以大哦，你要尋找的：O((M/N + N) log(N))。

Answer 2

如果你的整數是或多或少隨機^1），大多數比較只需要每個向量的前幾個整數（直到第一個不匹配）比較，所以在實踐中/平均

M（直覺相反）沒有對算法的複雜性沒有任何影響

爲了給你一些想法：即使，如果你的載體有無限長，最頻繁出現的整數有一個概率％，你需要小於2個的平均比較：

k < ∑ i*p^i = p/(1-p)^2 | p=0.5 
k < ∑ i*0.5^i = 2; 

對於其它概率的結果是：

60% -> k < 2.5 
70% -> k < 3.4 
80% -> k < 5.0 
90% -> k < 10.0 

請記住，所有這些數字上界爲整數比較的平均數和獨立元素的數量在向量中

^1）隨機我並不是指密碼意義上的隨機。這些數字甚至不必通過大多數隨機數字的質量測試。唯一的要求是它們不會以系統的方式形成相同的前綴 - 隨矢量長度增長。
除了惡意輸入之外，我目前無法想到一個不符合「或多或少隨機」的現實示例，但可能還有其他內容。