C++ 排序 vector 时间复杂度

Question

假设我有一个 vector<vector<int>> L有 N 个 vector ，总数为 int所有 vector 的总和最多为 M。标准 C++ 排序的最严格时间复杂度是多少 sort(L.begin(), L.end()) ？

vector<int>比较函数的运行时间最多为 O(M)，因此明显的界限是 O(NM log N)。但是如果我们实现标准归并排序，我们可以看到在每个 O(log N) 级别中，最多完成 O(M) 次整数比较，因此运行时间为 O((N+M) log N)。这是因为比较长度为 A 和 B 的两个 vector 需要 O(min(A,B)) 时间。

C++ 标准是否保证运行时间为 O((N+M) log N)？

Answer 1

没有足够的信息。您还需要知道 M 值在 N vector 中的分布。有了它，就可以直接找到整体复杂性:

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 返回 平均 每对内部 vector 之间的最小元素 数。

   • 例如，如果您有一个均匀分布，这是 平凡地等于 M/N。
5. 获取产品: 大 Oh = N·log(N)·E(M, N)·1。
   • 对于均匀分布，这将是M·log(N)。

您可以使用 Discrete Probability Distribution theory找出 E(M, N) 函数对于 N 上的 M 的任何分布是什么。

---

编辑 1:为了阐明这如何/为什么重要:考虑一个总是使我的 vector 看起来像这样的分布:

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) vector 比较的不同组合。

一个(并且只有一个)组合将进行 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) ，它可以进一步简化为您正在寻找的 Big Oh:O((M/N + N) log(N))。