考虑到我们每次走 k 个删一个,那么在一圈以内我们可以删掉 \left\lfloor\frac{n}{k}\right\rfloor 个,然后剩下了 n-\left\lfloor\frac{n}{k}\right\rfloor 个人。这时我们在第 \left\lfloor\frac{n}{k}\right\rfloor\cdot k 个人的位置上。而你发现这个东西它等于 n-n\bmod k 。于是我们继续递归处理,算完后还原它的相对位置。得到如下的算法:
1
2
3
4
5
6
7
8
9
10
11
12
intjosephus(intn,intk){if(n==1)return0;if(k==1)returnn-1;if(k>n)return(josephus(n-1,k)+k)%n;// 线性算法intres=josephus(n-n/k,k);res-=n%k;if(res<0)res+=n;// mod nelseres+=res/(k-1);// 还原位置returnres;}
可以证明这个算法的复杂度是 \Theta (k\log n) 的。我们设这个过程的递归次数是 x ,那么每一次问题规模会大致变成 \displaystyle n\left(1-\frac{1}{k}\right) ,于是得到
n\left(1-\frac{1}{k}\right)^x=1
解这个方程得到
x=-\frac{\ln n}{\ln\left(1-\frac{1}{k}\right)}
下面我们证明该算法的复杂度是 \Theta (k\log n) 的。
考虑 \displaystyle \lim _{k \rightarrow \infty} k \log \left(1-\frac{1}{k}\right) ,我们有