DeeCamp笔试题-Python代码分析

DeeCamp笔试环节遇到的代码分析题,通过一些数学式子上的化简来优化计算。我觉得我的想法还挺有意思的。文末有彩蛋哦~🍭

题目

假设可以不考虑计算机运行资源(如内存,堆栈)的限制,以下Python3代码预期的输出结果是?

1
2
3
4
5
6
def rec(n):
if n < 2:
return 1
return rec(n // 2) + rec(n // 4)

print(rec(12345678987654321))

分析

这个递归函数一看就是指数级别的时间复杂度,我试着跑了一下,1分钟没跑出来,我大概知道不是简单跑一跑就能出结果的(谁都知道吧)。

然后我试着分析一下这个式子,可以转为如下等式:
$$
rec(n)=\left\{\begin{matrix}
1 & n<2\\
rec(n//2) + rec(n//4) & n\geq2\\
\end{matrix}\right.\tag{1}
$$
这里的$//$符号表示整除,相当于数学式子中的向下取整,即$n//2 = \lfloor(n/2)\rfloor$,但我为了保持整个递推式的程序感,保留使用$//$符号。

现在假设n足够大,做如下推理:
$$
\begin{equation}
\begin{aligned}
rec(n) &= rec(n//2)+rec(n//4)\\
&= [rec((n//2)//2)+rec((n//2)//4)]+rec(n//4)\\
\end{aligned}
\end{equation}\tag{2}
$$
(2)式只是对$rec(n//2)$进行了再一次的展开,现在有一个问题,那么就是:$rec((n//2)//2)$是否等于$rec(n//4)$呢?不可以妄自下结论,可以证明一下。

证明

所有的正整数n都可以表示为$k$、$(k-1)+1$、$(k-2)+2$或$ (k-3)+3$中的某一个,其中$k$、$k-1$、$k-2$或$k-3$都是4的倍数。

那么就有:
$$
\begin{equation}
\begin{aligned}
n//2=&\left\{\begin{matrix}
k // 2 & \text{k is a multiple of 4}\\
(k-1) // 2+1//2 & \text{(k-1) is a multiple of 4}\\
(k-2) // 2+2//2 & \text{(k-2) is a multiple of 4}\\
(k-3) // 2+3//2 & \text{(k-3) is a multiple of 4}\\
\end{matrix}\right.\\
=&\left\{\begin{matrix}
k // 2 & \text{k is a multiple of 4}\\
(k-1) // 2 & \text{(k-1) is a multiple of 4}\\
(k-2) // 2+1 & \text{(k-2) is a multiple of 4}\\
(k-3) // 2+1 & \text{(k-3) is a multiple of 4}\\
\end{matrix}\right.\\
\end{aligned}
\end{equation}\tag{*}
$$
那么继续求得$(n//2)//2$的结果是
$$
\begin{equation}
\begin{aligned}
(n//2)//2
=&\left\{\begin{matrix}
k // 4 & \text{k is a multiple of 4}\\
(k-1) // 4 & \text{(k-1) is a multiple of 4}\\
(k-2) // 4+1//2 & \text{(k-2) is a multiple of 4}\\
(k-3) // 4+1//2 & \text{(k-3) is a multiple of 4}\\
\end{matrix}\right.\\
=&\left\{\begin{matrix}
k // 4 & \text{k is a multiple of 4}\\
(k-1) // 4 & \text{(k-1) is a multiple of 4}\\
(k-2) // 4 & \text{(k-2) is a multiple of 4}\\
(k-3) // 4 & \text{(k-3) is a multiple of 4}\\
\end{matrix}\right.\\
\end{aligned}
\end{equation}\tag{3}
$$
$n//4$的结果是
$$
\begin{equation}
\begin{aligned}
n//4
=&\left\{\begin{matrix}
k // 4 & \text{k is a multiple of 4}\\
(k-1) // 4+1//4 & \text{(k-1) is a multiple of 4}\\
(k-2) // 4+2//4 & \text{(k-2) is a multiple of 4}\\
(k-3) // 4+3//4 & \text{(k-3) is a multiple of 4}\\
\end{matrix}\right.\\
=&\left\{\begin{matrix}
k // 4 & \text{k is a multiple of 4}\\
(k-1) // 4 & \text{(k-1) is a multiple of 4}\\
(k-2) // 4 & \text{(k-2) is a multiple of 4}\\
(k-3) // 4 & \text{(k-3) is a multiple of 4}\\
\end{matrix}\right.\\
\end{aligned}
\end{equation}\tag{4}
$$
由(3)(4)式可得,$(n//2)//2=n//4$,即$rec((n//2)//2)=rec(n//4)$。

而且不仅仅是$(n//2)//2=n//4$,只要是整除号都可以把括号打开,证明同理。

证明到这一点后,(2)式又可以继续化简了:
$$
\begin{equation}
\begin{aligned}
rec(n) &= rec(n//2)+rec(n//4)\\
&= [rec((n//2)//2)+rec((n//2)//4)]+rec(n//4)\\
&= rec(n//4)+rec(n//8)+rec(n//4)\\
&= 2rec(n//4)+rec(n//8)\\
&= 2[rec(n//8)+rec(n//16)]+rec(n//8)\\
&= 3rec(n//8)+2rec(n//16)\\
&= 3[rec(n//16)+rec(n//32)]+2rec(n//16)\\
&= 5rec(n//16)+3rec(n//32)\\
&= 8rec(n//32)+5rec(n//64)\\
&= 13rec(n//64)+8rec(n//128)\\
&= …\\
\end{aligned}
\end{equation}\tag{5}
$$
写到这里会发现,这种展开式的系数是斐波那契数列,当n足够大时,有如下规律:
$$
rec(n)=fib(k+1)rec(n//2^k)+fib(k)rec(n//2^{k+1})\tag{6}
$$
其中$fib$是斐波那契函数,$fib(n)$表示斐波那契数列的第n项:
$$
fib(n)=\left\{\begin{matrix}
0 & n=0\\
1 & n=1\\
fib(n-1)+fib(n-2) & n\geq 2 \\
\end{matrix}\right.
$$
但是求得(6)式还是不顶用啊,因为(6)式依旧是一个递推式,这个递推式的底在哪呢?

这个递推式的底还是要根据$rec(n)$的底来定,$rec(n)$的底是$n<2$,也就是当$n<2$时,这个式子就不继续推下去了。

顺其自然思考,什么时候能够同时满足$n//2^k$和$n//2^{k+1}$都小于2呢?

  1. 当$2^{k+1}<n$时:

    $n//2^{k+1}\geq1$,那么就有$n//2^k \geq 2$,这不是递推式的底,还可以继续推下去。

  2. 当$2^k> n$时:

    $n//2^{k}=0$,但是求不出$n//2^{k+1}$,因为$n//2^{k}$已经是递推式的底了,推不到$rec(n//2^{k+1})$。

  3. 当$2^k\leq n\leq 2^{k+1}$时:

    $n//2^k=1$,而且$n//2^{k+1}=0$,两个都满足递推式底的条件。

综上,需要找一个k,使得n介于$2^k$和$2^{k+1}$之间。

回归题目,题目要求的数是$12345678987654321$,写一个Python脚本求这个k。

1
2
3
4
5
6
7
k = 0
n = 12345678987654321
while True:
if (2 ** k) <= n <= (2 ** (k+1)):
print(k)
break
k += 1

程序求得k=53时,$2^k\leq n\leq 2^{k+1}$。所以结果也就出来了:
$$
rec(12345678987654321)=fib(54)rec(1)+fib(53)rec(0)\tag{7}
$$
由(1)式知,$rec(1)=1$且$rec(0)=1$,所以(7)式再次写为:
$$
\begin{aligned}
rec(12345678987654321)
=&fib(54)+fib(53)\\
=&fib(55)\\
\end{aligned}
$$
结果就是斐波那契数列的第55项,其值为$139583862445$,这就是最终结果!

什么,你问我怎么快速求斐波那契数列的第n项,那可以看看我这篇文章,时间复杂度O(log(n))空间复杂度O(1)求斐波那契数列第n项,机智地打一波广告😉

后记

考场上可千万别像我这样算,看出有大量重复子问题,直接用记忆法,建个vector或者hashmap记录结果,也能秒破。我这个铁头娃就是非要搞证明,看到答案的一瞬间,又看到了时间正好到了交卷的那一刻。答案还没写呢,考试时间就到了。心痛!

我觉得我之所以没来得及写答案,macOS全屏状态下看不到时间有很大的锅,所以我在此安利一个软件:Clock Bar,装上了以后,可以在Touch Bar上看时间,再也不会全屏看不到时间而耽误一些事情了。而且设计风格很Apple😉。

image-20190617230657747

下载地址:https://github.com/nihalsharma/Clock-Bar/releases

或直接使用homebrew安装:brew cask install clock-bar

Nighty-night~




======================
全 文 结 束    感 谢 阅 读
======================