私は最近、Josephus 問題はデータ構造を使用して O(n) で解決できると主張するフォーラムに出くわしました。ここでの明確な選択は循環リンクリストですが、ウィキペディアで数学的な再帰的/反復的なジョセフスアルゴリズムを実行しない限り、O(kn) または O(n^2) でのみ実行できると主張します。まず最初に、循環リンク リストには、検索 O(n)、削除 O(1)、追加 O(1) というプロパティがあります。これは、delete が特定のノードであり、append が head または tail を置き換えていることを前提としています。
ノードの循環リストがある場合、次のように開始点から削除するノードを見つけることができます。
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 ノードになります (つまり、元の 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 が小さい場合、 k を遠ざけるだけで、まだ開始した場所には到達しません)。
とにかく、私のポイントは、O(n) のデータ構造を介してこれを行う方法がわからないということです。ウィキペディアの解決策は、再帰の力を示す O(n) の非常に洗練された数学的方法です (純粋にコール スタックによって古い開始点を追跡するなど) が、実際のオブジェクトを削除すると、O( n)。露骨に尋ねるだけでなく、これを理解しようとする試みを表示したかったので、データ構造を使用して O(n) でこれを行う方法を知っている人はいますか? ありがとう！