递归函数的时间复杂度应该怎么算?

Question

比如这个python快排的时间复杂度该怎么算

def q_sort(l):
    if len(l)<=1:
        return l
    else:
        return q_sort([x for x in l[1:] if x<l[0]])+[l[0]]+q_sort([x for x in l[1:] if x>=l[0]])

Answer 1

时间复杂度还是 N * lgN. 这么看, 把qsort递归看成一棵树, 每一层都处理 N 个元素, 树高度 lgN.

不过 这个程序 空间上费的多了吧. 貌似也是 N * lgN