证明 10 次交换存在 O(n) 算法
prove an O(n) algorithm exists for 10 swaps
一个著名的问题是找到用于排序数组的最小交换量。我的问题是我们有大小为 n 的数组，我们知道我们可以用 10 次交换对它进行排序（我们不知道移动，只知道移动的次数）。我想证明存在一个对这个数组进行排序的 O(n) 算法（对于时间）。
首先，为了证明这个说法，我应该提供一些代码吗？我不知道如何证明
其次，这与排序数组的最小交换量有关吗？
感谢您的帮助
如果我们知道 10 次交换就足以对数组进行排序，那么这个数组几乎已排序，最多 10*2 = 20 个元素乱序。因此，如果我们在几乎排序的数组上找到某种具有 O(n) 的排序算法，那么它就足以证明您的陈述。
例如我们可以使用两步解决方案：
找出数组中所有乱序元素，移除并保存
将保存的元素插入结果数组中正确的位置
使用这种“天真的”算法，在最坏的情况下，第一步需要一次通过，第二步需要 20 次或更少的通过（20 个乱序元素）。因此，如果 n >> 10 比你的情况得到 O(n)。如果不依赖于 n
，则此证明对于任何恒定数量的交换都是正确的
您的解决方案在 Adaptive sorts algorithms 中。
A classic example of an adaptive sorting algorithm is Straight Insertion Sort. In this sorting algorithm, we scan the input from left to right, repeatedly finding the position of the current item, and insert it into an array of previously sorted items.
我们知道：
The performance of this algorithm can be described in terms of the number of inversions in the input, and then T(n) will be roughly equal to I(A)+(n-1), where I(A) is the number of Inversions.
因此，对于您的情况，反转的次数是恒定的，该算法的复杂度将是 Theta(n)。
一个著名的问题是找到用于排序数组的最小交换量。我的问题是我们有大小为 n 的数组，我们知道我们可以用 10 次交换对它进行排序（我们不知道移动，只知道移动的次数）。我想证明存在一个对这个数组进行排序的 O(n) 算法（对于时间）。
首先，为了证明这个说法，我应该提供一些代码吗？我不知道如何证明 其次，这与排序数组的最小交换量有关吗？
感谢您的帮助
如果我们知道 10 次交换就足以对数组进行排序，那么这个数组几乎已排序，最多 10*2 = 20 个元素乱序。因此，如果我们在几乎排序的数组上找到某种具有 O(n) 的排序算法，那么它就足以证明您的陈述。
例如我们可以使用两步解决方案：
找出数组中所有乱序元素，移除并保存
将保存的元素插入结果数组中正确的位置
使用这种“天真的”算法，在最坏的情况下，第一步需要一次通过，第二步需要 20 次或更少的通过（20 个乱序元素）。因此，如果 n >> 10 比你的情况得到 O(n)。如果不依赖于 n
您的解决方案在 Adaptive sorts algorithms 中。
A classic example of an adaptive sorting algorithm is Straight Insertion Sort. In this sorting algorithm, we scan the input from left to right, repeatedly finding the position of the current item, and insert it into an array of previously sorted items.
我们知道：
The performance of this algorithm can be described in terms of the number of inversions in the input, and then
T(n)will be roughly equal toI(A)+(n-1), whereI(A)is the number of Inversions.
因此，对于您的情况，反转的次数是恒定的，该算法的复杂度将是 Theta(n)。