这些数字对我来说没有意义。为什么检查列表是否存在或检查列表的len()所花费的时间比copy()要长?它是O(1) vs O(n)个操作
Total time: 3.01392 s
File: all_combinations.py
Function: recurse at line 15
Line # Hits Time Per Hit % Time Line Contents
==============================================================
15 @profile
16 def recurse(in_arr, result=[]):
17 nonlocal count
18
19 1048576 311204.0 0.3 10.3 if not in_arr:
20 524288 141102.0 0.3 4.7 return
21
22 524288 193554.0 0.4 6.4 in_arr = in_arr.copy() # Note: this adds a O(n) operation
23
24 1572863 619102.0 0.4 20.5 for i in range(len(in_arr)):
25 1048575 541166.0 0.5 18.0 next = result + [in_arr.pop(0)]
26 1048575 854453.0 0.8 28.4 recurse(in_arr, next)
27 1048575 353342.0 0.3 11.7 count += 1
Total time: 2.84882 s
File: all_combinations.py
Function: recurse at line 38
Line # Hits Time Per Hit % Time Line Contents
==============================================================
38 @profile
39 def recurse(result=[], index=0):
40 nonlocal count
41 nonlocal in_arr
42
43 # base
44 1048576 374126.0 0.4 13.1 if index > len(in_arr):
45 return
46
47 # recur
48 2097151 846711.0 0.4 29.7 for i in range(index, len(in_arr)):
49 1048575 454619.0 0.4 16.0 next_result = result + [in_arr[i]]
50 1048575 838434.0 0.8 29.4 recurse(next_result, i + 1)
51 1048575 334930.0 0.3 11.8 count = count + 1
并不是复制本身比您提到的O(1)个操作花费的时间更长。
但是请记住，基本情况比递归情况运行的频率要高得多。
我不知道你说的" it ";在你的问题中。通用("皇家") ">不是需要更长的时间吗?您的实现需要更长的时间。在大多数语言实现中，len是O(1)，因为它是与对象中的任何更改一起维护的实例属性。这种存在的实现比较慢，因为它是循环的，而不是简单地遍历列表，尽管它仍然是O(N).