performance - 'Students and Lockers' 问题的最佳解决方案是什么？

Question

我认为展示一些经典的 CS 问题并让人们展示他们的算法优化技巧会很有趣。希望我们能够看到一些巧妙的技术来解决我们可以在实践中实现的抽象问题。

理想情况下，解决方案将以具有大 O 分类的伪代码呈现。这种分类的证据是肉汁。问题来了:

有 N 个封闭的储物柜和 N 个学生在场。第一个学生打开每个储物柜。第二个学生打开或关闭每第二个储物柜。这将继续，第 n 个学生打开和关闭每个第 n 个储物柜。过了N个同学，什么储物柜都打开了？打开多少个储物柜？

Answer 1

学生只会翻转他们的号码是其除数的那些储物柜的状态(学生 2 翻转偶数储物柜，学生 3 翻转可被 3 整除的储物柜，依此类推......)。因此，在 N 轮后唯一会保持打开状态的储物柜是那些具有奇数个除数的储物柜(因为它们开始关闭，奇数次翻转将使其打开)。唯一具有奇数除数的数字是完全平方数，因此所有完全平方数的储物柜都将保持打开状态。所以在 N 轮之后，打开的储物柜数量将是 N 的平方根(落地)。

这个解决方案需要 O(sqrt(N)) 才能知道 究竟是哪个储物柜是开放的，但是如果你只需要知道 O(1) 多少储物柜是开放的。