上楼梯问题的时间复杂度是o(n)还是 nlogn?# JobHunting - 待字闺中
T*7
1 楼
用dynamic programming的方法。
另外，如果我用纯c做这个题目 没有hashmap。怎么解决？还能得到相同的时间复杂度
么
另外，如果我用纯c做这个题目 没有hashmap。怎么解决？还能得到相同的时间复杂度
么
l*8
2 楼
problem:
有一段楼梯有n级台阶,规定每一步只能跨一级或两级或三级,要登上第n级台阶有几种不
同的走法?
solution:
let f(i) denote the number of different methods to climb the stairs.
Then
f(0) = 1
f(1) = 1
f(2) = 2
f(3) = f(0) + f(1) + f(2)
....
f(n) = f(n-3) + f(n-2) + f(n-1)
Is this what you talked about?
【在 T******7 的大作中提到】
: 用dynamic programming的方法。
: 另外，如果我用纯c做这个题目 没有hashmap。怎么解决？还能得到相同的时间复杂度
: 么
有一段楼梯有n级台阶,规定每一步只能跨一级或两级或三级,要登上第n级台阶有几种不
同的走法?
solution:
let f(i) denote the number of different methods to climb the stairs.
Then
f(0) = 1
f(1) = 1
f(2) = 2
f(3) = f(0) + f(1) + f(2)
....
f(n) = f(n-3) + f(n-2) + f(n-1)
Is this what you talked about?
【在 T******7 的大作中提到】
: 用dynamic programming的方法。
: 另外，如果我用纯c做这个题目 没有hashmap。怎么解决？还能得到相同的时间复杂度
: 么
c*p
3 楼
好像递推公式有点问题？
【在 l*********8 的大作中提到】
: problem:
: 有一段楼梯有n级台阶,规定每一步只能跨一级或两级或三级,要登上第n级台阶有几种不
: 同的走法?
: solution:
: let f(i) denote the number of different methods to climb the stairs.
: Then
: f(0) = 1
: f(1) = 1
: f(2) = 2
: f(3) = f(0) + f(1) + f(2)
【在 l*********8 的大作中提到】
: problem:
: 有一段楼梯有n级台阶,规定每一步只能跨一级或两级或三级,要登上第n级台阶有几种不
: 同的走法?
: solution:
: let f(i) denote the number of different methods to climb the stairs.
: Then
: f(0) = 1
: f(1) = 1
: f(2) = 2
: f(3) = f(0) + f(1) + f(2)
l*8
4 楼
let me think again....
【在 c****p 的大作中提到】
: 好像递推公式有点问题？
【在 c****p 的大作中提到】
: 好像递推公式有点问题？
c*p
5 楼
类fabonacci的问题应该都能得到复杂度为logn的解吧？
【在 T******7 的大作中提到】
: 用dynamic programming的方法。
: 另外，如果我用纯c做这个题目 没有hashmap。怎么解决？还能得到相同的时间复杂度
: 么
【在 T******7 的大作中提到】
: 用dynamic programming的方法。
: 另外，如果我用纯c做这个题目 没有hashmap。怎么解决？还能得到相同的时间复杂度
: 么
c*p
6 楼
好像是我想错了。。。
【在 c****p 的大作中提到】
: 好像递推公式有点问题？
【在 c****p 的大作中提到】
: 好像递推公式有点问题？
l*8
7 楼
I think it's correct.
【在 c****p 的大作中提到】
: 好像递推公式有点问题？
【在 c****p 的大作中提到】
: 好像递推公式有点问题？
g*e
8 楼
the runtime is O(n) space requirement is O(k) where k is the number of
different steps you can make each time.
different steps you can make each time.
c*p
9 楼
logk的时间复杂度和O(1)的空间复杂度就够了吧。。。
【在 g*********e 的大作中提到】
: the runtime is O(n) space requirement is O(k) where k is the number of
: different steps you can make each time.
【在 g*********e 的大作中提到】
: the runtime is O(n) space requirement is O(k) where k is the number of
: different steps you can make each time.
l*8
10 楼
应该是： O(k^3 * logn) 时间
O(k^2) 空间 吧？？
【在 c****p 的大作中提到】
: logk的时间复杂度和O(1)的空间复杂度就够了吧。。。
O(k^2) 空间 吧？？
【在 c****p 的大作中提到】
: logk的时间复杂度和O(1)的空间复杂度就够了吧。。。
c*p
11 楼
嗯，我那里的k就是n
【在 l*********8 的大作中提到】
: 应该是： O(k^3 * logn) 时间
: O(k^2) 空间 吧？？
【在 l*********8 的大作中提到】
: 应该是： O(k^3 * logn) 时间
: O(k^2) 空间 吧？？
p*2
12 楼
run time 为什么是logn呢？
不是要从1算到n吗？
不是要从1算到n吗？
l*8
13 楼
好像在CLRS 五六十页的地方讲过
【在 p*****2 的大作中提到】
: run time 为什么是logn呢？
: 不是要从1算到n吗？
【在 p*****2 的大作中提到】
: run time 为什么是logn呢？
: 不是要从1算到n吗？
l*a
14 楼
fibonacci serials
有个著名的log2n算法
不过我觉得面世中回答那个或者面试者要求那个
的话
真是无聊
【在 p*****2 的大作中提到】
: run time 为什么是logn呢？
: 不是要从1算到n吗？
有个著名的log2n算法
不过我觉得面世中回答那个或者面试者要求那个
的话
真是无聊
【在 p*****2 的大作中提到】
: run time 为什么是logn呢？
: 不是要从1算到n吗？
c*p
15 楼
[f1 f2 f3] = [f0 f1 f2] * A，
A= [0 0 1; 1 0 1; 0 1 1];
这样[fn fn+1 fn+2] = [f0 f1 f2] * A^n
其中A^n可以用二分法算，logn【 在 peking2 (myfacebook) 的大作中提到: 】
A= [0 0 1; 1 0 1; 0 1 1];
这样[fn fn+1 fn+2] = [f0 f1 f2] * A^n
其中A^n可以用二分法算，logn【 在 peking2 (myfacebook) 的大作中提到: 】
p*2
16 楼
mark一下先。多谢。
【在 c****p 的大作中提到】
: [f1 f2 f3] = [f0 f1 f2] * A，
: A= [0 0 1; 1 0 1; 0 1 1];
: 这样[fn fn+1 fn+2] = [f0 f1 f2] * A^n
: 其中A^n可以用二分法算，logn【 在 peking2 (myfacebook) 的大作中提到: 】
s*n
17 楼
费波纳切不是O(1)的时间复杂度么，这个推推也能搞出个公式吧
a*m
18 楼
为啥A是[0 0 1; 1 0 1; 0 1 1]? 感觉是010; 001; 111，或者是俺想差了？
【在 c****p 的大作中提到】
: [f1 f2 f3] = [f0 f1 f2] * A，
: A= [0 0 1; 1 0 1; 0 1 1];
: 这样[fn fn+1 fn+2] = [f0 f1 f2] * A^n
: 其中A^n可以用二分法算，logn【 在 peking2 (myfacebook) 的大作中提到: 】
【在 c****p 的大作中提到】
: [f1 f2 f3] = [f0 f1 f2] * A，
: A= [0 0 1; 1 0 1; 0 1 1];
: 这样[fn fn+1 fn+2] = [f0 f1 f2] * A^n
: 其中A^n可以用二分法算，logn【 在 peking2 (myfacebook) 的大作中提到: 】
l*8
19 楼
你说的是这个吧：
Fn 约等于 1/sqrt(5) * （1.618...）^ n (黄金分割数的n次方）
算n次方也要O(logn)的
【在 s******n 的大作中提到】
: 费波纳切不是O(1)的时间复杂度么，这个推推也能搞出个公式吧
Fn 约等于 1/sqrt(5) * （1.618...）^ n (黄金分割数的n次方）
算n次方也要O(logn)的
【在 s******n 的大作中提到】
: 费波纳切不是O(1)的时间复杂度么，这个推推也能搞出个公式吧
相关阅读
狗家16年hardware summer intern有消息了吗？有人了解Netflix的senior data analyst职位吗Georgia Tech 的 online CS master 有用吗？请问个公司选组的问题：Hbase还是Kafka？？ESTA签证可以面试吗求内推，统计phd夏天毕业Director of Engineering position in Bay Area startupO1 的专业相关性求Android Developer职位内推请问哪儿可以找biotech start up 的工作招人－software developer ruby离职后手里的文章什么的怎么算amat招SEM，EDX的application engineer.opt extension被RFE了，要了employment history感觉现在招人的bar好高啊。被吓到了新人求教，面试时 要不要和hm透露已经拿到的offer和其他面试情况？狗的天顶星技术其实就是字符串收索。大部分人还认为阿法狗在背棋谱请问G这道题目怎么做？问个问题某A血汗工厂在湾区招2-3年经验的吗？