图解算法(四)

进入图解算法四,看完这一章对一些概念性的东西有了一些理解,在这里记录下。

分而治之----一种著名的递归式问题解决的方法:

D&C的思想就是不断将问题缩小规模,知道符合基线条件(基线条件通常是数组为空或者只包含一个元素),快速排序就是一种使用了D&C的经典例子

快速排序代码如下:

def quick_sort(arr):
    if len(arr) < 2:
        return arr    #基线条件
    else:
        pivot = arr[0]      #基准值
        less = [i for i in arr[1:] if i <= pivot]
        grater = [i for i in arr[1:] if i > pivot]
    return quick_sort(less) + [pivot] + quick_sort(grater)

print(quick_sort([10, 5, 3, 54, 23]))

快速排序速度很快,运行时间为O(nlog^n),但是在最遭的情况下很慢,运行时间为 O(n^2 )。

最遭情况:一般来说会选择第一个值作为基准值,如果元素在有序的情况下,左边总会得到一个空的数组,调用的高度会达到很大,这是最遭的情况。调用的栈多,栈长为O(n),每层需要的时间为O(n),运行时间为
O(n) * O(n) = O(n^2)

最佳情况:如果每次选择的基准值都可以将数组分为两半,那么就不需要那么多递归调用,调用栈也就少,栈长为O(log^n), 每层需要的时间为O(n),运行时间为 O(log^n) * O(n) = O(nlog^n)

小结:

 >1D&C的主要思想就是将问题逐步分解,直到问题达到基线条件结束
  2实现快速排序时,基准值最好随机选择,这样出现最糟情况的概率就会极小
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 这篇文章是《图解算法》一书的摘抄总结。原书标题是《Grokking Algorithms》,grok是中文“意会”...
    SeanCheney阅读 3,142评论 0 14
  • 1 序 2016年6月25日夜,帝都,天下着大雨,拖着行李箱和同学在校门口照了最后一张合照,搬离寝室打车去了提前租...
    RichardJieChen阅读 5,165评论 0 12
  • 立秋新雨后的夜晚,夹杂着些许的凉意,小南裹着被单,躺在床上,如往常一般翻着一本旧书。 手机里的信息提示音响了很多下...
    可可夏荫阅读 649评论 2 7
  • map的介绍 map的结构就是key与value的形式,但它存储是无序的,它是引用类型,其实在某种程度上面说,ma...
    astarblog阅读 1,526评论 0 0
  • 怀着激动的心情,轩辕出发了,离开自己生活了十八年的部落,到外面的广阔天空寻找自己的归宿。 一路上他不紧不慢的赶路,...
    地无疆阅读 130评论 0 0