algorithm - Josephus 概率在 O(n) 中使用循环列表

Question

我最近偶然发现一个论坛声称可以使用数据结构在 O(n) 中解决 Josephus 问题。这里明确的选择是循环链表，但我声称它只能在 O(kn) 或 O(n^2) 中完成，除非你使用维基百科的数学递归/迭代 josephus 算法。首先，循环链表具有以下属性:搜索 O(n)、删除 O(1)、追加 O(1)。这假设 delete 是给定的节点，而 append 正在替换头或尾。

如果我们有一个循环节点列表，我们可以从起点找到要删除的节点，如下所示:

n = 6 个节点

k = 删除每第 3 个节点

起点:节点#0

节点:0、1、2、3、4、5

我们可以通过 (k + StartingPoint - 1) % n 来计算删除哪个节点。对于起点 = 0，我们有 (3 + 0 - 1) % 6 = 2。现在，3 将是我们的起点。 (3 + 3 - 1) % 5 = 0，当移动时是我们原来的 5 节点(即，数字现在是 0,1,2,3,4，因为原来的 2 已经不存在了)。这基本上就是数学版本的工作原理。对于链表，我们可以类似地推导出哪个节点需要删除。问题是我们必须前往这个节点。链表有 O(n) 搜索，这是一个问题。于是我们遍历到这个节点，将其删除，现在有n = n-1。我们找到下一个索引，进行 O(n) 搜索，得到 n = n_original - 2。这变成 n + (n-1) + (n-2) + ... = O(n^2)。

如果我们有一个双向链接的循环列表，那么如果节点离我们更近，我们就不必绕一圈。尽管如此，如果 k 小于 n，这是 O(k) 搜索，如果 k 大于 n，这是 O(n) 搜索(因为在到达起点之前你只能移动 n 个节点，但如果 k 很小，你只需要将 k 移开，你就不会到达你开始的地方)。

无论如何，我的观点是我不明白如何通过复杂度为 O(n) 的数据结构来做到这一点。维基百科上的解决方案是 O(n) 中一种非常优雅的数学方法，它显示了递归的强大功能(仅通过调用堆栈等来跟踪旧起点)，但是当删除实际对象时，似乎不可能得到 O( n).我想展示我试图解决这个问题的尝试，而不仅仅是公然询问，所以有人知道在 O(n) 中使用某种数据结构来做到这一点的方法吗？谢谢!

Answer 1

我在 my blog 处用 O(n) 时间的循环链表解决了这个问题.该网站还有一个使用队列的 O(n) 解决方案和一个使用普通(非循环)链表的 O(n^2) 解决方案。使用循环链表，您总是向前移动，永远不会后退，正如您对双向链表所建议的那样。

例如，查看您的列表。你从 0 开始，数 3，删除项目 3。然后数 3，删除 0。然后数 3，删除 4。然后数 3，删除 2。然后数 3，删除 5。最后数 3，删除 1。总计所采取的步数为 kn，其中 n 是节点数，k 是步长。但这是节点数的 O(n)，因为 n 是问题大小，k 是常数。