S*h
2 楼
fib(k)本来就是指数级增长，不需要O（n)的时间吧
【在 r**d 的大作中提到】
: 给定一个数n, 找到k
: so that fib(k)<=n
: 有没有好于O(n)的方法？
【在 r**d 的大作中提到】
: 给定一个数n, 找到k
: so that fib(k)<=n
: 有没有好于O(n)的方法？
k*p
3 楼
fib计算有lgn的解法，按照这样的计算，自然不需要o （n）
b*e
4 楼
log_{a}^{n}, where a = 1.618.
【在 r**d 的大作中提到】
: 给定一个数n, 找到k
: so that fib(k)<=n
: 有没有好于O(n)的方法？
【在 r**d 的大作中提到】
: 给定一个数n, 找到k
: so that fib(k)<=n
: 有没有好于O(n)的方法？
v*t
5 楼
好像是 O(logklogk)
【在 r**d 的大作中提到】
: 给定一个数n, 找到k
: so that fib(k)<=n
: 有没有好于O(n)的方法？
【在 r**d 的大作中提到】
: 给定一个数n, 找到k
: so that fib(k)<=n
: 有没有好于O(n)的方法？
h*6
6 楼
根据通项公式，有O(1)的算法。
d*l
7 楼
我当时是类似这样的一题。似乎他想要的并不是更好的方法，而是只是想让你写出朴素
的方法，然后考虑整数溢出的情况，把函数写的健壮一点。把细节都弄到位他应该就满
意了。fib数列确实有logn的做法，但不太易于实现。另外用通项会有乘方运算，其实
也并不是O(1)的，应该还是logn的
的方法，然后考虑整数溢出的情况，把函数写的健壮一点。把细节都弄到位他应该就满
意了。fib数列确实有logn的做法，但不太易于实现。另外用通项会有乘方运算，其实
也并不是O(1)的，应该还是logn的
相关阅读
求推荐南加H1B公司帮朋友安利一下，airbnb帝都office疯狂招人这年头弯曲人的BSO的多了 (转载)offer 求比较请问flg和supa的offer怎么选？求转job hunting版 (转载)fb contract 转正容易吗？Comcast Sunnyvale Office 招聘 Sr. QA Tech LeadH1b approve后取消offerTic Tac Toe 检查是否获胜的最优解是啥？询问这两个Offer的选择，工资多点股票少点；工资少点股票多点这种情况还要不要跟ex老板联系招software engineer选大公司还是继续在小公司混请教面试时写完算法，让写个test case是写什么？Water and Jug Problem面试的时候给哪个答案好【转】Uber- 非常可怕 《在Uber奇怪的一年》找INTERN,接受OPT，可以E-VERIFY,SUNNYVALE CA (转载)A9和Amazon其他部门工资一样吗？Middleware Admin 工作， 13 万年薪Morgan Stanley上海Business Analyst 职位，有必要面吗 (转载)