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~

Image