我正在为松散耦合的集群编写一些代码。为了在作业期间实现最佳性能，我让集群在每次孩子进入或退出时重新映射其数据。这最终将成为可选的，但目前它默认执行其数据平衡。我的平衡基本上只是确保每个孩子的文件数量永远不会超过每台机器的平均文件数，再加上一个。如果除法不干净，则加一用于余数。而且由于余数总是小于孩子的数量[除了 0 的情况，但我们可以排除这种情况]，平衡后的孩子最多 avg + 1。

一切似乎都很好，直到我意识到我的算法是 O(n!)。顺着孩子的名单往下看，找出平均数，余数，谁有太多，谁有太少。对于太多列表中的每个孩子，遍历列表，发送给每个太少的孩子。

有没有更好的解决方案？我觉得应该有。

编辑：这里有一些伪代码来展示我是如何导出 O(n!) 的：

编辑：O(n^2)。Foreach n, n => n*n => n^2。我想我今天早上没有喝足够的咖啡！;)

将来我想转向更灵活和有弹性的分布方法[权重和启发式]，但现在，数据的统一分布是可行的。

我在 Reddit 上看到了这个问题，并没有提出积极的解决方案，我认为在这里问这个问题是一个完美的问题。这是关于面试问题的线程：

编写一个方法，该方法接受一个大小为 m 的 int 数组，如果该数组由数字 n...n+m-1、该范围内的所有数字和该范围内的数字组成，则返回 (True/False)。不保证对数组进行排序。（例如，{2,3,4} 将返回 true。{1,3,1} 将返回 false，{1,2,4} 将返回 false。

我遇到的问题是我的面试官一直要求我进行优化（更快的 O(n)、更少的内存等），以至于他声称你可以使用恒定数量的数组在一次遍历中做到这一点记忆。从来没想过那个。

连同您的解决方案，请说明他们是否假定数组包含唯一项目。还要指出您的解决方案是否假定序列从 1 开始。（我稍微修改了问题以允许出现 2、3、4 的情况......）

编辑：我现在认为不存在处理重复的时间线性和空间常数算法。任何人都可以验证这一点吗？

重复问题归结为测试数组是否在 O(n) 时间、O(1) 空间中包含重复项。如果可以做到这一点，您可以先简单地测试，如果没有重复，则运行发布的算法。那么你能在 O(n) 时间 O(1) 空间中测试欺骗吗？

是否有所有内容的 Big-O 符号的主列表？数据结构、算法、对每个执行的操作、平均情况、最坏情况等。