约瑟夫问题(Josephus problem)的klog(n)解法

约瑟夫问题是一个经典的算法问题，其解决过程涉可能用到的数据结构有数组、链表，涉及的算法包括模拟、递归、递推、动态规划等等，因此非常适合做一道面试题。

问题描述：

首先n个候选人围成一个圈，依次编号为0..n-1。然后指定一个正整数k，并0号候选人开始按从1到k的顺序依次报数，n-1号候选人报数之后，又再次从0开始。当有人报到K时，这个人被淘汰，从圈里出去。下一个人从1开始重新报数。重复上述过程，直至剩下一个人，求问最后这一人在最开始的圈中的编号。

例如，n=5（共有5个人），k=3（每次第三个人出列）时，问题的解是3（最后剩下编号为3的人）

关于其背景的描述可以参考 百度百科-约瑟夫问题 和 Wikipedia-Josephus problem

约瑟夫问题存在多种解法:

1. 最朴素的使用数组的模拟方法，时间复杂度O(n^2)
2. 使用链表(队列)改进的模拟方法，时间复杂度O(nk)
3. 使用直接递推的方法，复杂度O(n)
4. 使用一次前进多步的递推方法，复杂度O(klog(n))

其中1-3的解法，已有很多文章进行了介绍，可以参见 Josephus problem - The general case， 百度百科-约瑟夫问题

复杂度O(n)的解法

我们简单对解法3进行说明如下：

                |------------  k  -----------|

使用n表示候选人人数 n>=1，k表示每轮淘汰第k个人，k>=1。n个人组成的约瑟夫环可以记为A，使用 f(n) 表示约瑟夫环A的解。

当淘汰第k个人后，从编号 k mod n 开始剩下的n-1个人（编号从0开始），组成一个新的约瑟夫环B，此时这个n-1个人组成的新问题的解为f(n-1)。由于B中编号相对于A中后移了k位，因此已知B的解 f(n-1)，A的解为 f(n)=(f(n-1)+k) mod n;

注意到问题的边界条件：当 n=1时 f(n,k) = 0，因此可以从i=1开始一直递推到n得到 f(n,k)：

即

写成程序就是

int forSmallN(int n, int k) {

        int s=0;

        for (int i = 2; i <=n ; i++) s = (s + k) % i;

        return s;

}

复杂度O(klog(n))的解法

上述解法中，问题的规模每次减少1，因此复杂度是O(n)，有没有可能进一步提高问题的缩减速度呢？尤其是当k<<n的时候，直观上理解，可以一次性排除多个人，从而更加快速的对问题的规模进行缩减。

永曾曾经在《约瑟夫环问题》一文中通过对照新旧序列编号提出了一种基于递归的方法，但是当n十分大时，容易造成stackoverflow的异常。我们需要考虑直接递推的方法。

一种方式是直接从递推公式  入手：当k<<i 时，(f(i-1)+k) 大部分情况下小于i，此时计算mod i是没有必要的，因此可以进一步缩减问题规模，找到最大的x，使得 f(i-x)+x*k<i。关于此种解法，可以参考 约瑟夫问题（优化优化再优化）。然鹅，此方法受限于f(i-x)的大小，不能每次都保证最大程度的缩减问题规模，实验也可证明这一点。因此本文从另一个角度入手：

考虑如下例子，其中k=3，从A环中在回到原点前按规则尽量剔除多个人，得到另一个约瑟夫环B

             |--------  k  --------|    |--------  k  ---------|

设length(A) = j, length(B) = i, 则容易得到如下关系（其中除法均取下整）

j = i/(k-1)*k + i%(k-1)

其中 i/(k-1) 则表示A中被剔除掉的人的个数，且有 j-i = i/(k-1)。

因此按此方式递归，每次问题的规模可以缩减i/(k-1)。

假设B的解为 f(i)=s，问题转化为，已知 i, j,  以及 f(i)=s 求A的解f(j).

通过下图研究A与B之间序号的对应关系

一般情况下各个区间长度标注如下：

                 | -----------------   l=(j-i)*k   ---------------------|   | r= j- (j-i)*k |

                                                            s

注意到相比于一次减少一个问题规模解法（f(n)=(f(n-1)+k) mod n），s如果在B中不同位置，对应到A中的坐标右移量可能不同，但是可以通过s本身推导得出

为了便于理解和表达，记 l=(j-i)*k, r=j-l=j- (j-i)*k

当 s<r 时（例如s=0），相对于A中右移了l位，因此 f(j) = (s+l)%j

因为 s<r，从而 s+l<l+r=j，从而有 f(j) = (s+l) = (s+j-r)

当 s>=r 时 （例如s=3），还要计算因为额外剔除人所产生的位移，而这部分位移刚好为 (s- r)/(k-1)，此时

   
综上，当 k>1时

注意到我们得出递推公式，从而避免函数的嵌套调用，但是递推过程的最后，有可能出现 j>n 的情况，如下图

因此需要判断 j是否大于n，如果大于n则取 j=n，之后的计算过程一致。注意到当 i<k 时可以直接使用递推表达式 f(i) = (f(i-1)+k)%i

复杂度分析

从上述过程可以得出，从i=1开始，每次增量 i += i/(k-1) 直到 i>=n，即

其中m为迭代轮数

为了验证  与 k 的阶数，求其商的导数

当k=2时上式值为0.15

当k=3时上式值为0.06

当k=10时上式值为0.0055

当k趋于无穷时上式值趋于0

因此可以认为 与 k同阶

从而