下面是代码:
import time
def rec1(len):
if( len < 2): return 1;
return 2*rec1(len-1);
def rec2(len):
if( len < 2): return 1;
return rec2(len-1) + rec2(len-1);
def callAndReport(len, method):
time1 = time.time()
answer = method(len)
time2 = time.time()
print("{0} with {1}:{2} in {3:.0f} ms".format(len,method.__name__,answer, (time2-time1)*1000))
if __name__ == '__main__':
callAndReport(20,rec1)
callAndReport(20,rec2)
print('')
callAndReport(23,rec1)
callAndReport(23,rec2)
此代码生成以下输出:
20 with rec1:524288 in 0 ms
20 with rec2:524288 in 642 ms
23 with rec1:4194304 in 0 ms
23 with rec2:4194304 in 4613 ms
有人能解释一下执行时间差吗?我没有什么主意,但我想确定一下。你知道吗
为了完整性,我遇到的最初问题是下面的方法(可以很容易地表示为For循环,但这不是重点):
def find11s_rec(len):
if len<2: return 0
if len== 2: return 1;
return find11s_rec(len-2)+find11s_rec(len-1)+2**(len-2)
是的。你知道吗
那是因为
rec1
只使用rec1
一次,而rec2
使用rec2
两次。然后那些内部rec2
调用将分别调用rec2
两次。函数调用的数量将呈指数增长。当rec1
可能使用x
调用时,rec2
将使用2^x
调用。在计算机科学术语中,rec1
是O(x),而rec2
是O(2^x)。在更复杂的情况下,危险的递归可能是无效的;所以使用调试器来找出实际执行的操作。你知道吗rec1
的复杂度为O(n),rec2
的复杂度为O(2^n)。这是一个很大的性能差异。你知道吗相关问题 更多 >
编程相关推荐