algorithm - 我的算法可以做得更好吗？

Question

我面临着为一项任务制定最有效算法的挑战。现在我来到了 n * logn 的复杂性。我想知道是否有可能做得更好。所以基本上任务是让 children 玩数数游戏。给你的数字 n 是 child 的数量，m 是你在执行之前跳过某人的次数。您需要返回一个给出执行顺序的列表。我试着这样做，你使用跳过列表。

Current = m
while table.size>0:
    executed.add(table[current%table.size])
    table.remove(current%table.size)
    Current += m

我的问题是这是否正确？它是 n*logn，你能做得更好吗？

Answer 1

Is this correct?

没有。 当您从表中删除一个元素时，table.size 会减小，并且 current % table.size 表达式通常最终会指向另一个不相关的元素。 例如，44 % 11 是 0 但 44 % 10 是 4，这是一个完全不同位置的元素.

Is it n*logn?

没有。 如果 table 只是一个随机访问数组，它可以执行 n 操作来删除一个元素。 例如，如果 m = 1，程序在修正上述点后，总是会删除数组的第一个元素。 当数组实现足够简单时，每次都需要 table.size 操作来重新定位数组，导致总共大约 n^2/2 操作。

现在，将是 n log n 如果 table 被备份，例如，通过具有隐式索引的平衡二叉搜索树而不是键，以及拆分和合并原语。这是一个陷阱，例如，here是快速搜索英文资源的结果。 这样的数据结构可以用作访问、合并和拆分成本为 O(log n) 的数组。 但到目前为止，没有任何迹象表明是这种情况，而且大多数语言的标准库中都没有这样的数据结构。

Can you do it better?

更正:部分，是；完全，也许。

如果我们向后解决问题，我们有以下子问题。

设一圈k个 child ，指针当前在 child t。 我们知道，就在刚才，有一圈 k + 1 child ，但我们不知道指针在哪里，在哪个 child x 上。 然后我们数到 m，去掉 kid，指针结束在 t。 我们刚刚删除了谁，x 是什么？

原来“x 是什么”部分可以在 O(1) 中解决(绘图在这里很有帮助)，所以找到最后一个站着的 child 是在 O(n) 中可行。 正如评论中指出的那样，整个过程称为 Josephus Problem ，及其变体得到了广泛研究，例如，在 Knuth 等人的《具体数学》中。

但是，在每步 O(1) 中，这只会找到最后一个站着的 child 的号码。 它不会自动给出计算 child 出局的完整顺序。 当然有一些方法可以使每一步 O(log(n))，总共 O(n log(n))。 但是至于O(1)，我暂时不知道。