h*********2
发帖数: 444 | 1 先是写pow(x, n)
recursive和iterative哗哗哗写完了
面试官来了个，
What is the minimum number of multiplications for calculating pow(x, n)?
然后给我举了个例子，要算x^45
iterative的方法是
x --> x^2 --> x^4 --> x^8 --> x^16 --> x^32
然后把x, x^4, x^8, x^32 乘起来
总共需要5 + 3 = 8次乘法
recursive的方法是
x^45 = x^22 * x^22 * x
x^22 = x^11 * x^11
x^11 = x^5 * x^5 * x
x^5 = x^2 * x^2 * x
x^2 = x * x
这样也是需要8次乘法
但是有更好的办法是
x --> x^2 --> x^4 --> x^8
x * x^8 = x^9
x^9 --> x^18 --> x^36
x^9 * x^36 = x^45
这样只需要3 + 1 + 2 + 1 = 7次乘法
然后我就傻了。
查了下，这个问题还蛮出名：
https://en.wikipedia.org/wiki/Addition-chain_exponentiation
不过也太超出45分钟面试的范畴了吧……
虽然整个过程还挺和谐，走的时候人家还说了句最后那题是bonus, 心里还是惴惴不安 |
m*******h
发帖数: 78 | 2 不是log n 吗? 最后那个问题就相当于变向的问你时间复杂度吧 |
q*****l
发帖数: 124 | 3 不是标准的divide and conquer么。。。。 |
n**s
发帖数: 2230 | 4 这就是只知道背题而不思考的结果。知其然不知其所以然。
思路很明显的是divide and conquer，但和普通的这类问题比，区别在于不用两边都算
， 只要算一边即可。
时间复杂度就是 T(n)=T(n/2)+c. 很容易推出T=O(logn) |
h*********2
发帖数: 444 | 5 楼上的在说话之前起码先去看看我给的链接好吗。
根本不是问时间复杂度，而是问具体到底多少次乘法是最少。二分法不能保证是最优的。
面试官当时给我举了个例子，
要算x^45
iterative的方法是
x --> x^2 --> x^4 --> x^8 --> x^16 --> x^32
然后把x, x^4, x^8, x^32 乘起来
总共需要5 + 3 = 8次乘法
recursive的方法是
x^45 = x^22 * x^22 * x
x^22 = x^11 * x^11
x^11 = x^5 * x^5 * x
x^5 = x^2 * x^2 * x
x^2 = x * x
这样也是需要8次乘法
但是有更好的办法是
x --> x^2 --> x^4 --> x^8
x * x^8 = x^9
x^9 --> x^18 --> x^36
x^9 * x^36 = x^45
这样只需要3 + 1 + 2 + 1 = 7次乘法
现在问题是，对于任意给定的n，怎么找到这个最优的方案？ |
f*******w
发帖数: 1243 | 6 wiki上不说了是NP-complete的么……而且DP也没办法解决
那面试官最后有没有说怎么做？ |
