递归函数时间复杂度的评估
我想要的
我正在尝试找出一个函数的时间复杂度。
评估算法每一步的复杂度，以及整个函数的复杂度。
1 def deep_copy(ls): 2 new=[] 3 for e in ls: 4 if type(e) == list: 5 new.append(deep_copy(e)) 6 else: 7 new.append(e) 8 return new
我尝试过的
我知道第2、4、6和8行的复杂度都是
O(1)。最好的情况是被复制的列表里只有简单的元素（也就是说，里面没有列表）。
如果是这样的话，第7行的复杂度最大为
O(n)，那么第3行的for循环的复杂度就是O(n·n) = O(n²)。所以对于一个有n个简单元素的列表，整个函数的复杂度就是O(n²)。现在，假设我们有一个包含
n个列表的列表，每个列表里有n个元素。根据之前的结果，我知道第5行的复杂度是O(n³)，因为它是一个O(n²)的操作嵌套在一个O(n)的操作里。第3行的复杂度会是O(n⁴)，因为第5行执行了n次，所以这个情况下的整体复杂度是O(n⁴)。对于一个包含
n个列表的列表，每个列表又包含n个列表，每个列表里有n个元素，第5行的复杂度会是O(n⁵)，因此整个循环和函数的复杂度就是O(n⁶)。
问题是什么
我很清楚，复杂度不仅取决于列表的长度，还取决于列表的深度。
我认为这个函数的复杂度是 O(n^(2·k))，其中 k 是深度。
对于一个简单的列表，k = 1；对于一个简单列表的列表，k = 2；以此类推。
这个分析正确吗？如果不正确，哪里有问题，正确的答案是什么？
3 个回答
另一方面，假设你有
def deep_copy(ls):
new=[]
for e in ls:
if type(e) == list:
new = new + [deep_copy(e)]
else:
new = new + [e]
return new
new = new + [...] 是 O(n)。那么这到底是什么时间复杂度呢？
根据我之前的回答，
T(l) = O(len(l)) * [T(lᵢ) or O(1)] + O(1)
我们知道在 [] 里面的每条路径的成本多了一个 O(len(l))。
T(l) = O(len(l)) * [T(lᵢ) + O(len(l)) or O(1) + O(len(l))] + O(1)
= O(len(l)) * [(T(lᵢ) or O(1)) + O(len(l))] + O(1)
但是通过展开括号，我们就得到了：
T(l) = O(len(l)) * [T(lᵢ) or O(1)] + O(len(l))·O(len(l)) + O(1)
= O(len(l)) * [T(lᵢ) or O(1)] + O(len(l)²)
这意味着我们的成本是
O(sum(square of number of items in each list, including all sublists))
所以对于一个维度为 (n, n, n, ..., n)，有 i 个维度的情况，我们有
O(
n² + first level; one list of length n
n · n² + second level; n lists of length n
n · n · n² + third level; n² lists of length n
... +
nⁱ⁻¹ · n² "i"th level; nⁱ⁻¹ lists of length n
)
这就是
O(Σn^k from k=0 to k=i-1) · O(n²) +
= O(nⁱ⁺¹ + i) = O(nⁱ⁺¹) as i+1 ≥ 2
这并不意外，因为 Rob Watts 在使用 O(n) 的追加操作时也是这样。
我们来看一下这个函数，并且参考一下行号。同时，感谢@Veedrac指出在Python中，append操作的时间复杂度是O(1)。
1 def deep_copy(ls):
2 new=[]
3 for e in ls:
4 if type(e) == list:
5 new.append(deep_copy(e))
6 else:
7 new.append(e)
8 return new
就像你说的，第二、第四、第六和第八行的时间复杂度都是O(1)。第七行也是O(1)，而第三行是O(n)，也就是循环执行的时间复杂度。所以我们要关注的是第五行的时间复杂度。
第五行大致可以理解为：
_ = deep_copy(e)
new.append(_)
那么，这一行的时间复杂度是多少呢？它等于deep_copy(e)的时间复杂度 加上 append的时间复杂度 - O(1)。如果e里面没有任何列表，那么第五行的时间复杂度就是O(n)，这样整个函数的时间复杂度就变成O(n^2)。所以，时间复杂度不是O(n^(2*k))，而应该是O(n^k)。
不过，到目前为止，n是用来表示列表的长度。如果我们用n来表示所有列表中元素的总数呢？我还没有仔细分析过基于元素总数的时间复杂度，但这应该是值得研究的。
编辑： 我更新了我的计算，以反映append的时间复杂度是O(1)。另外，@Veedrac也让我确认了，把n看作元素总数是有用的。
你可能被一个不太准确的定义搞混了。还有，你似乎认为 append 操作的时间复杂度是 O(n)，其实并不是，它的时间复杂度是 O(1)。
想象一下在一个列表 l 上进行某个操作，所需的时间是 T(l)。
new=[]
for e in ls:
if type(e) == list:
new.append(deep_copy(e))
else:
new.append(e)
return new
就是
O(1) + [O(1) assign]
O(len(l)) * ( [len(l) loops + O(1) overhead for each loop]
(O(1) + [O(1) if]
O(1) + T(lᵢ)) or [O(1) append and T(lᵢ) recursion]
(O(1) + [O(1) else]
O(1)) [O(1) append]
) + O(1) [O(1) return]
这其实就是
T(l) = O(len(l)) * [T(lᵢ) or O(1)] + O(1)
需要注意的是，因为 T(lᵢ) 或 O(1) 这个时间复杂度同时取决于 lᵢ 的类型和 i 的值，所以我们不能像平常那样简单地解决这个递归问题。
我们的递归可以在非方形甚至非矩形的数组上工作。这意味着我们不能仅仅用 n 来表示列表的长度。
相反，我们可以用不同的量来表示。
我们知道这个递归会遍历 N 个元素。也就是说，我们会得到类似于
[
T(l₁) +
T(l₂) +
T(l₃) +
T(l₄) +
...
] + O(1)
这其实就是
[
[T(l₁₁) + T(l₁₂) + T(l₁₃) + T(l₁₄) + ... + O(1)] +
[T(l₂₁) + T(l₂₂) + T(l₂₃) + T(l₂₄) + ... + O(1)] +
[T(l₃₁) + T(l₃₂) + T(l₃₃) + T(l₃₄) + ... + O(1)] +
[T(l₄₁) + T(l₄₂) + T(l₄₃) + T(l₄₄) + ... + O(1)] +
...
] + O(1)
也就是
[
[T(l₁₁) + T(l₁₂) + T(l₁₃) + T(l₁₄) + ...] +
[T(l₂₁) + T(l₂₂) + T(l₂₃) + T(l₂₄) + ...] +
[T(l₃₁) + T(l₃₂) + T(l₃₃) + T(l₃₄) + ...] +
[T(l₄₁) + T(l₄₂) + T(l₄₃) + T(l₄₄) + ...] +
...
] + O(1) + T(len(l))
递归展开后是
[
[[[[...[O(1) + O(1) + ...]...]]]] +
[[[[...[...]...]]]] +
[[[[...[...]...]]]] +
[[[[...[...]...]]]] +
...
] + O(1) + O(len(l)) +
+ O(len(l₁)) + ... + O(len(l₄)) + ... +
+ O(len(l₁₁) + ... + O(len(l₄₄)) + ... +
+ O(len(l₁₁₁) + ...
+ ...
第一部分（在 [] 中）加起来是 O(N)。第二部分是所有列表长度的 总和。
显然，所有列表长度的总和至少和基础元素的总数一样大。不过，我们不能仅仅用基础元素的数量作为答案，因为
[[[...[[[[1]]]...]]]
这个操作需要花费相当长的时间来复制，但它只有一个元素。
所以我们的答案是
O(sum(number of items in each list, including all sublists))
那么为什么不直接用 n 或 N 或其他东西来表示呢？为什么只是一段文字呢？
其实，这就是你所需要的，也是你能给出的。如果你有另一个定义，比如：
数组的维度是
(x₁, x₂, x₃, ..., xₙ)。
那么你可以 接着用变量来解决（O(Σx + Πx)）。但这并不是问题所给出的内容。
注意，之前提到的 O(nⁱ⁺¹) 对于维度为 (n, n, n, ..., n) 的情况（有 i 个维度）并不完全正确。它应该是 O(nⁱ + i)。
现在，我做了一件很奇怪的事。我没有写 O(nⁱ + i) = O(nⁱ)。
当你有两个变量时，通常（但并不总是）值得考虑只有一个变量很大的情况。通常情况下 O(nⁱ) > O(i)，但是如果 n 和 i 可以是任意值，那么你可以让 n = 1，这时 O(nⁱ) < O(i)。
基本上，O(nⁱ + i) = O(nⁱ) 仅当你希望如此。如果情况是 n = 1 且 i 很大，那么就要包括 + i。否则，就不需要。
我们可以快速测试一下，幂是 i 而不是 i+1，通过设置 i=1 并进行计时：
SETUP="
def deep_copy(ls):
new=[]
for e in ls:
if type(e) == list:
new.append(deep_copy(e))
else:
new.append(e)
return new
"
python -m timeit -s "$SETUP" -s "x = [0] * 10**5" "deep_copy(x)"
python -m timeit -s "$SETUP" -s "x = [0] * 10**6" "deep_copy(x)"
结果是
10 loops, best of 3: 20.8 msec per loop
10 loops, best of 3: 209 msec per loop
当长度增加10时，所花费的时间增加了10倍，这说明是线性成本，正如我所说的。