algorithm - 试图证明/反驳算法的复杂性分析

Question

我不是在寻找上述问题的算法。我只是希望有人对我的回答发表评论。

我在面试中被问到以下问题:

How to get top 100 numbers out of a large set of numbers (can't fit in memory)

这就是我所说的:

将数字分成一批，每批 1000 个。在“O(1)”时间内对每批处理进行排序。到目前为止所用的总时间是 O(n)。现在从第一批和第二批中取出第一个 100 个数字(在 O(1) 中)。从上面计算的编号和第三批中取第一个 100，依此类推。这总共需要 O(n) - 所以它是一个 O(n) 算法。

面试官回答说要分拣一批1000个。不会花费 O(1) 时间，因此不会从一批中挑选出第 100 个，经过大量讨论后他说，他对算法花费 O(n) 时间没有问题，他只是有我说对批处理进行排序需要 O(1) 时间，这是一个问题。

我的解释是 1000 不依赖于输入 (n)。不管 n 是多少，我总是会批量生产 1000 个 nos。如果您必须计算，则排序需要 O(1000*log 1000))，这实际上是 O(1)。

如果非要好好算算的话，应该是

1000*log 1000 排序一批对 (n/1000) 个这样的批处理进行排序需要 1000 * log 1000 * n/1000 = O(n*log(1000)) 时间 = O(n) 时间

我也问过我的很多 friend 这个问题，虽然他们同意我的观点，但只是部分同意。所以我不想知道我的推理是否100%正确(即使是99%正确也请批评)。

请记住，这篇文章并不是要回答上面发布的问题。我已经在 Retrieving the top 100 numbers from one hundred million of numbers 找到了更好的答案

Answer 1

面试官错了，但考虑原因很有用。你说的是正确的，但你依赖一个未说明的假设。可能，面试官正在做出不同的假设。

如果我们说对 1000 个数字进行排序是 O(1)，我们就有点不正式了。具体来说，我们的意思是，在N趋于无穷大的极限内，有一个常数大于或等于对1000个数进行排序的代价。由于对固定大小集合进行排序的成本与 N 无关，因此该限制也不取决于 N。因此，随着 N 趋于无穷大，它的复杂度为 O(1)。

一个大方的解释是，面试官希望你以不同的方式对待排序步骤。您可以更精确地说，随着 M 趋于无穷大(或者 M 趋于 N，如果您愿意)，它是 O(M*log(M))，其中 M 代表数字批处理的大小。这将使您的方法的总体 O(N*log(M)) 成为可能，因为 N 和 M 都接近无穷大。当然，这不是你描述的限制。

严格来说，不指定极限就说某事是 O(1) 是没有意义的。人们通常不需要为算法操心，因为从上下文中可以清楚地看出:通常采用的极限是单个参数接近无穷大。仅考虑 N 时，您的描述是正确的，但您可以考虑的不仅仅是 N。