Muf*_*ous 5 arrays algorithm optimization big-o array-algorithms
想象一下，有一个整数数组，但不允许您访问任何值（因此不允许Arr[i] > Arr[i+1]或其他）。区分整数的唯一方法是使用query()函数：该函数将元素子集作为输入，并返回该子集中唯一整数的数量。目标是根据整数的值将它们分成组 \xe2\x80\x94 同一组中的整数应具有相同的值，而不同组中的整数应具有不同的值。\n问题 - 代码必须是 O( nlog(n))，或者换句话说，query() 函数只能被调用 O(nlog(n)) 次。
我花了几个小时在 Python 中优化不同的算法，但所有这些算法的复杂度都是 O(n^2)。作为参考，这是我开始的代码：
\nn = 100\nquerycalls = 0\nsecretarray = [random.randint(0, n-1) for i in range(n)]\ndef query(items):\n global querycalls\n querycalls += 1\n return len(set(items))\ngroups = []\nsecretarray生成一个长度为 的巨大随机数字列表n。querycalls跟踪函数被调用的次数。groups是结果所在。
我做的第一件事是尝试创建一个基于合并排序的算法（将数组拆分，然后根据 query() 值合并），但我永远无法使其低于 O(n^2)。
\n假设您有一个元素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)时间。