O (n)에서 순환 목록을 사용하는 Josephus prob

Question

최근 Josephus 문제가 O (n)에서 데이터 구조로 해결 될 수 있다고 주장하는 포럼을 발견했습니다. 여기서 명확한 선택은 순환 연결된 목록이지만, 수학적 재귀/반복 조셉 스피어 알고리즘 인 wikipedia를 사용하지 않는 한 O (kn) 또는 O (n^2)에서만 수행 할 수 있다고 주장합니다. 먼저 순환 링크 된 목록에는 다음과 같은 속성이 있습니다. 검색 O (n), 삭제 O (1), 추가 O (1). 이것은 삭제가 주어진 노드이고 append가 머리 또는 꼬리를 대체한다고 가정합니다.

K = 모든 3 노드를 삭제

StartingPoint을

N = 6 노드 : 우리는 노드의 원형 목록이있는 경우 다음과 같이

, 우리는 시작 지점에서 삭제할 노드를 찾을 수 있습니다 : 노드 # 0

노드 0, 1, 2, 3, 4, 5

우리는 (K + StartingPoint - 1)를 통해 삭제 된 노드 계산할 수 % 않음. 시작점 = 0 인 경우 (3 + 0 - 1) % 6 = 2입니다. 이제 3이 시작점이됩니다. (3 + 3 - 1) % 5 = 0, 원래의 5 노드로 바뀌었을 때 (즉 원래의 2가 없어 졌으므로 숫자는 이제 0,1,2,3,4가됩니다). 그것은 기본적으로 수학적 버전이 작동하는 방식입니다. 링크 된 목록의 경우, 노드를 삭제해야하는 노드를 파생시킬 수 있습니다. 문제는이 노드로 이동해야한다는 것입니다. 링크 된 목록에는 문제가되는 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가 작 으면 O 당신은 k를 멀리 움직여야 만합니다.

상관없이, O (n)의 데이터 구조를 통해이 작업을 수행하는 방법을 알지 못합니다. 위키피디아의 솔루션은 재귀의 힘을 보여주는 O (n)의 매우 우아한 수학적 방법입니다 (호출 스택에 의한 오래된 시작점을 추적하는 것 등). 그러나 실제 객체를 삭제하면 O를 얻는 것이 불가능 해 보입니다. 엔). 나는 이것을 알아 내고 단지 뻔뻔스럽게 물어 보려는 시도를 보이기를 원했기 때문에 어떤 데이터 구조로 O (n)에서 이것을 수행하는 방법을 아는 사람이 있습니까? 감사!

Answer 1

이 문제는 O (n) 시간에 순환 링크 된 목록 my blog에서 해결됩니다. 이 웹 사이트에는 일반 (원형이 아닌) 링크 된 목록을 사용하는 대기열과 O (n^2) 솔루션을 사용하는 O (n) 솔루션도 있습니다. 순환 연결 목록을 사용하면 이중 연결 목록으로 제안 할 때 항상 앞으로, 결코 뒤로 이동할 수 없습니다.

예를 들어, 귀하의 목록을보십시오. 당신은 0에서 시작하고, 3을 카운트하고, 3을 삭제합니다. 그리고 3을 세고 0을 삭제합니다. 그리고 3을 세고 4를 삭제하십시오. 그리고 3을 세고 2를 삭제하십시오. 그리고 3을 세고 5를 삭제하십시오. 취해진 단계의 수는 kn이며, 여기서 n은 노드의 수이고, k는 단계 크기이다. 그러나 n은 문제 크기이고 k는 상수이기 때문에 이것은 노드 수의 O (n)입니다.