问个complexity问题# JobHunting - 待字闺中
c*a
1 楼
def func(i):
if i==0:
return
return func(i-1) or func(i-1)
这个是不是 o(n^2)?
return T(n-1) or T(n-1)看起来像这样
if i==0:
return
return func(i-1) or func(i-1)
这个是不是 o(n^2)?
return T(n-1) or T(n-1)看起来像这样
j*s
2 楼
T(n) = T(n-1) + f(n)
if f(n) = O(n), then it is O(n^2).
so it depends
if f(n) = O(n), then it is O(n^2).
so it depends
S*w
3 楼
是的
【在 c*****a 的大作中提到】
: def func(i):
: if i==0:
: return
: return func(i-1) or func(i-1)
: 这个是不是 o(n^2)?
: return T(n-1) or T(n-1)看起来像这样
【在 c*****a 的大作中提到】
: def func(i):
: if i==0:
: return
: return func(i-1) or func(i-1)
: 这个是不是 o(n^2)?
: return T(n-1) or T(n-1)看起来像这样
W*g
4 楼
不懂，没有返回值还可以or？
【在 c*****a 的大作中提到】
: def func(i):
: if i==0:
: return
: return func(i-1) or func(i-1)
: 这个是不是 o(n^2)?
: return T(n-1) or T(n-1)看起来像这样
【在 c*****a 的大作中提到】
: def func(i):
: if i==0:
: return
: return func(i-1) or func(i-1)
: 这个是不是 o(n^2)?
: return T(n-1) or T(n-1)看起来像这样
a*m
5 楼
似乎是2^n
【在 c*****a 的大作中提到】
: def func(i):
: if i==0:
: return
: return func(i-1) or func(i-1)
: 这个是不是 o(n^2)?
: return T(n-1) or T(n-1)看起来像这样
【在 c*****a 的大作中提到】
: def func(i):
: if i==0:
: return
: return func(i-1) or func(i-1)
: 这个是不是 o(n^2)?
: return T(n-1) or T(n-1)看起来像这样
t*g
6 楼
看不懂，求解释
c*a
7 楼
恩...2^n
2 possible choice,
(2 choose 1) (2 choose 1)...n of them
2 possible choice,
(2 choose 1) (2 choose 1)...n of them
s*s
8 楼
应该是2^n， 不是n^2
【在 c*****a 的大作中提到】
: def func(i):
: if i==0:
: return
: return func(i-1) or func(i-1)
: 这个是不是 o(n^2)?
: return T(n-1) or T(n-1)看起来像这样
【在 c*****a 的大作中提到】
: def func(i):
: if i==0:
: return
: return func(i-1) or func(i-1)
: 这个是不是 o(n^2)?
: return T(n-1) or T(n-1)看起来像这样
相关阅读