主题：【原创】由一个简单的面试题想起的 -- 东方射日

F(N,P)=Min{(L-1)*(1+F(L-1,P-1))/N+(1+F(N-L,P))*(N-L)/N} 你的表达式里缺了三个1，最后一个非常重要。（其实现在这个表达式也不全对，L=1，N时不成立，但是这不影响下面的分析，因为N很大时我们相信最小值不会在L=1或N时取到）

显然有F(N,P+1)<=F(N,P)…………………………………(1)

只考虑N>>1的情况。用归纳法证明F(N,P)∽A(P)N^B(P)，B(P)<=1，并求出A(P)，B(P)。

P=1时命题成立。现在假设F(N,P)∽A(P)N^B(P)成立，计算F(N,P+1)。可以合理地假设取到最小值的那个L满足1<<L<<N………………………(2)

把(1+F(L-1,P-1))*(L-1)/N+(1+F(N-L,P))*(N-L)/N对L/N展开，并考虑条件(1)，得

(1+F(L-1,P-1))*(L-1)/N+(1+F(N-L,P))*(N-L)/N

≈F(N,P+1)+1-L(F(N,P+1)+NF'(N,P+1))/N+A(P)/N*L^(B(P)+1)+无穷小量。

对L求导得到最小值，按定义这个最小值就是F(N,P+1)，也就是说

1-L(F(N,P+1)+NF'(N,P+1))/N+A(P)/N*L^(B(P)+1)的最小值必须是零。由此可以得到

F(N,P+1)+NF'(N,P+1)≈c*N^(B(P)/(1+B(P))，因此F(N,P+1)≈A(P+1)N^B(P+1)，

这里的B(P)=1/P，A(P)=P/(P+1)(P!)^(1/P)

当P趋于无穷大时A(P)≈(P-1)/e+Log[2πP]/(2e)。

L(P)∽N^(1-1/P)*P/(P!)^(1/P)

愿意的话可以进一步算得

F(N,P)=P/(P+1)(P!)^(1/P)*N^(1/P)+C(P)+o(1)

C(1)=1/2，C(P)=(P-2)/2，P>1

L(P)∽N^(1-1/P)*P/P!^(1/P)+D(P)+o(D(P))

D(P)=-N^(1-2/P)*P(P-1)/(P!)^(2/P)/2

可以把它们组合成更紧凑的形式L(P)∽E*(N-E/2*N^(1-1/P))^(1-1/P)

E=P/P!^(1/P)

实际值与近似值的差

P=2 F(N,2)-(Sqrt[8N/9]-4/3/Sqrt[N])

P=3 F(N,3)-((81N/32)^(1/3)+1/2)

P=4 F(N,4)-((6144N/625)^(1/4)+1)

F(N，2)的进一步估计

F(N，2)≈(8N/9)^(1/2)-4/3/Sqrt[N]+Abs[Cos[πSqrt[2N]]]/(π(Sqrt[π N]-5))，最后一项分母里的常数不是太靠得住。

“量子化”条件：当Sqrt(2N)=n+1/2时估计式(8N/9)^(1/2)-4/3/Sqrt[N]的精确度特别高，此时L=n，当

Sqrt(2N)=n时精确度最差，此时L=n-1/2。

点：F(N,2)-(Sqrt[8N/9]-4/3/Sqrt[N])

红线：Abs[Cos[πSqrt[2N]]]/(π(Sqrt[π N]-5))

F(N，P)里总是有一些振荡现象，这是因为近似计算时总假设N，L为实数，但实际上它们只能是整

数。猜想这些振荡可以用Abs[Cos[πP(N/P!)^(1/P)+Pπ/2]]/N^(1/P)来很好地逼近。比较麻烦的是

F(N，P)的振荡会遗传给F(N，P+1)。这会使得寻找参数的难度变大。