python - 计算嵌套列表中元素的递归函数的大 O

Question

def f(L):
 if L == []:
  return 0
 return (f(L[0]) if type (L[0]) == list else 1) + f(L[1:])

我在确定递归函数的大 O 时遇到了一些麻烦。我有一种感觉，这个函数是 O(n*m)，其中 n 是列表 L 的长度，m 是列表 L 中列表元素的长度。我是对的还是这个函数只是 O(n)？

Answer 1

让我们有另一个功能 g(l)做什么 f(L)但与 l , L 的列表元素.
所有递归调用的扩展如下:

step 0: f(L)
        |        \
step 1: g(L[0]) + f(L[1:])
                  |        \
step 2:           g(L[1]) + f(L[2:])
                            |        \
step 3:                     g(L[2]) + f(L[3:])
                                      |        \
                                      ...       ...

数量 f节点是 O(n) .
数量 g节点是 O(n) .
对于每一步， f节点占用 O(1)和 g节点占用 O(m)因为

step i.0: g(l)
          |   \
step i.1: 1 +  g(l[1:])
               |       \
step i.2:      1 +      g(l[2:])
                        |       \
step i.3:               1 +      g(l[3:])
                                 |       \
                                 1 +      ...

我相信，那么， O(n * 1 + n * m) = O(n*m) .
如果我错了，请纠正我。