上下文
这个问题源于试图最小化昂贵函数调用的数量
问题定义
请注意 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) 的函数,它返回对列表进行排序所需的 最小调用次数?
最佳答案
答案是是。
这个问题本质上等同于找到 longest increasing subsequence (LIS) 在一个数组中,您可以使用算法来解决这个问题。
为什么这道题等价于最长递增子序列?
因为每个extract_and_insert
操作都将在其最有效的使用中更正数组中恰好 一个元素的相对 位置。换句话说,当我们考虑数组的最长递增子序列的长度时,每次操作都会将该长度增加1。因此,所需的最少调用次数为:
length_of_array - length_of_LIS
因此,通过找到 LIS 的长度,我们将能够找到所需的最少操作数。
请阅读链接的维基百科页面以了解如何实现该算法。
关于algorithm - 排序列表所需的最少提取 + 插入次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22602129/