Проба Джозефуса с использованием кругового списка в O(n)

Question

Я недавно наткнулся на форум, утверждая, что проблема Иосифа может быть решена в O(n) с помощью структуры данных. Явным выбором здесь является круговой связанный список, но я утверждаю, что это можно сделать только в O(kn) или O(n^2), если вы не выполняете математический рекурсивный / итеративный алгоритм Джозефуса в виде wikipedia. Прежде всего, круговой связанный список имеет следующие свойства: Поиск O(n), Удалить O(1), Добавить O(1). Это предполагает, что delete - это заданный узел, а append заменяет голову или хвост.

Если у нас есть круговой список узлов, мы можем найти узел для удаления из начальной точки следующим образом:

n = 6 узлов

k = удалить каждый третий узел

StartingPoint: узел № 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).

Если бы у нас был дважды связанный круговой список, то нам не пришлось бы обходить весь путь, если бы узел был ближе к нам. Тем не менее, это O(k) поиск, если k меньше n, и O(n) поиск, если k больше n (так как вы можете когда-либо перемещать n узлов только тогда, когда вы начнете, но если k мало, вам нужно всего лишь отодвинуть k, и вы еще не достигнете того, с чего начали).

В любом случае, я не понимаю, как вы могли бы сделать это с помощью структуры данных в O(n). Решение в википедии - это очень элегантный математический способ в O(n), который показывает силу рекурсии (отслеживание старых начальных точек исключительно с помощью стека вызовов и т. Д.), Но при удалении реальных объектов кажется невозможным получить O (п). Я хотел показать свои попытки выяснить это, а не просто нагло спросить, так кто-нибудь знает способ сделать это в O(n) с некоторой структурой данных? Спасибо!

Answer 1

Я решаю эту проблему с помощью круглого связанного списка в 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 - это константа.