比如这个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]])
时间复杂度还是 N * lgN. 这么看, 把qsort递归看成一棵树, 每一层都处理 N 个元素, 树高度 lgN.
不过 这个程序 空间上费的多了吧. 貌似也是 N * lgN