Python递归函数时间复杂度如何判断，python递归函数判断,比如这个python快排

文章由Byrx.net分享于2019-03-23 06:03:31评论（118）

Python递归函数时间复杂度如何判断，python递归函数判断,比如这个python快排


比如这个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

编橙之家文章，

相关内容

评论关闭

最新python问答

python~HOT