上楼梯问题的时间复杂度是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)的时间复杂度么，这个推推也能搞出个公式吧
相关阅读
推广刷题 新东方这些行为都是汉奸卖国贼行为有没有mm整个holiday season都刷题？这绝对是中国孩子最省钱却最好的出路吧？工作人贩帖，想去【上海】工作的毕业1年内的看过来其实无人车很早就有了并且流行“苹果” 的待遇问题，请教Business Logic layer是干嘛的？面试应不应该考刷题是看立场的什么是MTS2 Software Engineer?有在SpaceX的马工吗？求建议关于swjtuer的Uber观你们公司的产品是怎么push到production的？java里的try-with resource没听说过面试给过么请教Google onsite第五轮都会问啥？offer选择比较 (转载)关于 F1 OPT 期间换工作H1B附加费飙升至$4000没人吐槽今年加州非常冷吗？ (转载)Python面试的概念题？