algorithm - 排序列表所需的最少提取 + 插入次数

Question

上下文

这个问题源于试图最小化昂贵函数调用的数量

问题定义

请注意 extract_and_insert != swap。特别是，我们从“from”位置获取元素，将其插入到“to”位置，然后SHIFT所有中间元素。

int n;
int A[n]; // all elements are integer and distinct



function extract_and_insert(from, to) {

  int old_value = A[from]

  if (from < to) {
    for(int i = from; i < to; ++i)
      A[i] = A[i+1];
    A[to] = old_value;
  } else {
    for(int i = from; i > to; --i)
      A[i] = A[i-1];
     A[to] = old_value;
  }
}

问题

我们知道有 O(n log n) 种算法可以对数字列表进行排序。

现在:是否有一个复杂度为 O(n log n) 的函数，它返回对列表进行排序所需的 最小调用次数？

Answer 1

答案是是。

这个问题本质上等同于找到 longest increasing subsequence (LIS) 在一个数组中，您可以使用算法来解决这个问题。

为什么这道题等价于最长递增子序列？

因为每个extract_and_insert 操作都将在其最有效的使用中更正数组中恰好 一个元素的相对 位置。换句话说，当我们考虑数组的最长递增子序列的长度时，每次操作都会将该长度增加1。因此，所需的最少调用次数为:

length_of_array - length_of_LIS

因此，通过找到 LIS 的长度，我们将能够找到所需的最少操作数。

请阅读链接的维基百科页面以了解如何实现该算法。