mak*_*ver 6 sorting algorithm data-structures
给定一个数组a和整数k.有人使用以下算法来获得前k个最小元素:
cnt = 0
for i in [1, k]:
for j in [i + 1, n]:
if a[i] > a[j]:
swap(a[i], a[j])
cnt = cnt + 1
问题是:如何计算cnt(当我们获得最终的k-排序数组时)的值,即交换数量,O(n log n)或更好？
或者简单地说:计算使用上述算法排序的第一个k最小数字所需的交换次数,小于O(n log n).
我正在考虑一个二叉搜索树,但我感到困惑(当增加i时,数组将如何变化？如何计算固定i的交换次数？...).
这是一个非常好的问题：它涉及逆对、堆栈和一些证明技术。
注1：下面使用的所有索引都是从1开始的，而不是传统的从0开始。
注2：如果想直接看算法，请从底部开始阅读。
首先我们将逆对定义为：
对于
a[i]和a[j]，其中i < j成立，如果我们有a[i] > a[j]，则a[i]和a[j]被称为逆对。
例如，在以下数组中：
3 2 1 5 4
a[1]和a[2]是一对逆对，a[2]并且a[3]是另一对。
在开始分析之前，我们先定义一个通用语言：在帖子的重置中，“从i”开始的逆对是指涉及 的逆对的总数a[i]。
例如，对于a = {3, 1, 2}，从 1 开始的逆对是 2，从 2 开始的逆对是 0。
现在让我们看一些事实：
i < j < k、 、a[i] > a[k]、a[j] > a[k]，则交换a[i]和a[j]（如果它们是逆对）不会影响从 开始的逆对的总数j；a = {5, 3, 4}，在与a[1]交换之前a[2]，从 1 开始的逆对总数为 2，但交换后，数组变为a = {3, 5, 4}，从 1 开始的逆对数量变为1）；A和 2 个数字，a并且b作为 的头元素，如果我们可以与A形成更多的逆对，我们有；aba > bi让我们表示从as开始的逆对的总数ip[i]，然后我们有：如果k是最小数满足ip[i] > ip[i + k]，则a[i] > a[i + k]whilea[i] < a[i + 1 .. i + k - 1]必须为真。换句话说，如果ip[i + k]是第一个小于 的数ip[i]，a[i + k]也是第一个小于 的数a[i]；第1点的证明：
根据逆对的定义，对于所有与a[k],k > j形成逆对的a[j]，a[k] < a[j]必须成立。由于a[i]和a[j]是一对逆元 且前提是i < j，我们有a[i] > a[j]。因此，我们有a[i] > a[j] > a[k]，这表明逆对关系没有被破坏。
证明第3点：
留空，因为很明显。
第4点的证明：
首先，很容易看出，当i < j,时a[i] > a[j]，我们有ip[i] >= ip[j] + 1 > ip[j]。那么，它的反矛盾命题也是成立的，即当i < j,时ip[i] <= ip[j]，我们有a[i] <= a[j]。
现在回到正题。由于 k 是满足 的最小数ip[i] > ip[i + k]，因此我们有ip[i] <= ip[i + 1 .. i + k - 1]，这a[i] <= a[i + 1.. i + k - 1]由我们刚刚证明的引理表明，这也表明该区域 中不存在逆对[i + 1, i + k - 1]。因此，与从 开始但涉及 的ip[i]逆对的数量相同。给定，我们知道 的逆对比区域中的要少，这表明（由点 3）。i + ka[i]ip[i + k] < ip[i]a[i + k]a[i][i + k + 1, n]a[i + k] < a[i]
你可以写下一些序列并尝试上面提到的 4 个事实并说服自己或反驳它们:P
现在是关于算法的。
一个简单的实现需要O(nk)计算结果，最坏的情况是O(n^2)当k = n。
但是我们如何利用上面的事实：
首先，我们ip[i]使用 Fenwick Tree 进行计算（参见下面的注释 1），这需要O(n log n)构建并O(n log n)计算所有内容ip[i]。
接下来，我们需要利用事实。由于 2 个数字的交换仅影响当前位置的逆对数字，而不影响（点 1 和 2）之后的值，因此我们不需要担心值的变化。此外，由于最接近右侧的较小数字在ip和 中共享相同的索引a，因此我们只需要找到第一个ip[j]小于 的数字。如果我们将第一个元素排序的交换次数表示为，则有。ip[i][i + 1, n]if[i]f[i] = f[j] + 1
但如何快速找到这个“第一个较小的数”呢？使用堆栈！这是一篇提出高度相似问题的帖子：给定一个数组 A，计算 B st B[i] 存储 A[i] 左侧最近的元素，该元素小于 A[i]
简而言之，我们能够在O(n).
但是等等，帖子说“向左”，但在我们的例子中它是“向右”。解决方案很简单：我们在我们的例子中向后做，然后一切都一样：D
因此，综上所述，算法的总时间复杂度为O(n log n) + O(n) = O(n log n)。
最后，我们用一个例子来谈谈（评论中@make_lover的例子的简化示例）：
a = {2, 5, 3, 4, 1, 6},k = 2
首先，让我们得到逆对：
ip = {1, 3, 1, 1, 0, 0}
为了计算f[i]，我们向后进行（因为我们需要使用堆栈技术）：
f[6] = 0, since it's the last one
f[5] = 0, since we could not find any number that is smaller than 0
f[4] = f[5] + 1 = 1, since ip[5] is the first smaller number to the right
f[3] = f[5] + 1 = 1, since ip[5] is the first smaller number to the right
f[2] = f[3] + 1 = 2, since ip[3] is the first smaller number to the right
f[1] = f[5] + 1 = 1, since ip[5] is the first smaller number to the right
所以，ans = f[1] + f[2] = 3
注1：使用Fenwick Tree（二叉索引树）获取逆对可以在O(N log N)中完成，这里有一篇关于这个主题的文章，请看一下:)
更新
2014 年 8 月 20 日：我之前的帖子中有一个严重错误（感谢@make_lover），这是最新的更新。