在不使用比较运算符的情况下对 nlog(n) 时间内的整数数组进行排序

Question

假设有一个整数数组，但不允许您访问任何值（所以没有 Arr[i] > Arr[i+1] 或其他）。区分整数的唯一方法是使用 query() 函数：此函数将元素的子集作为输入，returns 中唯一整数的数量这个子集。目标是根据整数的值将整数分成组——同一组中的整数应具有相同的值，而不同组中的整数应具有不同的值。问题 - 代码必须为 O(nlog(n))，或者换句话说，query() 函数只能被调用 O(nlog(n)) 次。

我花了几个小时优化 Python 中的不同算法，但所有算法都是 O(n^2)。作为参考，这是我开始的代码：

n = 100
querycalls = 0
secretarray = [random.randint(0, n-1) for i in range(n)]
def query(items):
    global querycalls
    querycalls += 1
    return len(set(items))
groups = []

secretarray 生成一个巨大的随机数字列表，长度为 n。 querycalls 跟踪函数被调用的次数。 groups 是结果所在。

我做的第一件事是尝试创建一个基于合并排序的算法（拆分数组，然后根据 query() 值合并）但我永远无法将其低于 O(n^2) .

Answer 1

假设您有一个元素 x 和一个包含不同元素的数组 A = [x0, x1, ..., x_{k-1}] 并且想知道 x 是否等同于数组中的某个元素，如果是, 到哪个元素。

你可以做的是一个简单的递归（我们称之为check-eq）：

检查是否 query([x, A]) == k + 1。如果是，那么您就知道 x 不同于 A.
否则，您知道 x 等价于 A 的某个元素。让A1 = A[:k/2], A2 = A[k/2+1:]。如果 query([x, A1]) == len(A1)，那么你知道 x 等价于 A1 中的某个元素，因此在 A1 中递归。否则递归 A2.

此递归最多需要 O(logk) 步。现在，让我们的初始数组为 T = [x0, x1, ..., x_{n-1}]。 A 将是一组“代表”元素的数组。你要做的是先取 A = [x0] 和 x = x1。现在使用 check-eq 来查看 x1 是否与 x0 在同一组中。如果否，则让A = [x0, x1]。否则什么都不做。继续 x = x2。你可以看看它是怎么回事。

复杂度当然是 O(nlogn)，因为 check-eq 被调用了 n-1 次，每次调用需要 O(logn) 次。

在不使用比较运算符的情况下对 nlog(n) 时间内的整数数组进行排序

Sorting an array of integers in nlog(n) time without using comparison operators

arrays

algorithm

optimization

big-o

array-algorithms