2

我不是在寻找上述问题的算法。我只想有人评论我的答案。

我在一次采访中被问到以下问题：

如何从大量数字中获取前 100 个数字（无法放入内存）

这就是我所说的：

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

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

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

如果您必须进行适当的计算，那将是

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

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

请记住，这篇文章并不是要回答上述问题。我已经在从一亿个数字中检索前 100 个数字中找到了更好的答案

4

2 回答 2

2

确实如此O(n)- 但是常量非常高，特别是考虑到您需要从文件系统中读取每个元素两次[一次在排序中，一次在第二阶段]，并且文件系统访问比内存访问慢得多。由于这可能是算法的瓶颈，因此您的解决方案可能会比使用优先级队列慢两倍。

请注意，对于一个常数top 100，即使是天真的解决方案也是O(n)：

for each i in range(1,100):
   x <- find highest element
   remove x from the list
   append x to the solution

这个解决方案也是O(n)，因为你有 100 次迭代，在每次迭代中你需要 2 次遍历列表 [通过一些优化，每次迭代可以完成 1 次遍历]。因此，遍历的总数严格小于 1000，并且没有更多取决于大小的因素，因此解决方案是O(n)- 但它绝对是一个糟糕的解决方案。

我认为面试官的意思是你的解决方案 - 虽然O(n)有很大的常数。

于 2012-04-16T07:18:47.767 回答
2

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

如果我们说对 1000 个数字进行排序是 O(1)，我们有点不正式。具体来说，我们的意思是，在 N 趋于无穷大的极限中，有一个常数大于或等于对 1000 个数字进行排序的成本。由于对固定大小集进行排序的成本与 N 无关，因此限制也不取决于 N。因此，当 N 趋于无穷时，它是 O(1)。

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

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

于 2012-04-16T09:29:57.197 回答