算法导论-1

四.(1)堆排序 第一次听堆排序是在107lab听忠哥讲的,但是没讲怎么实现.那时刚看了数据结 构的二叉树,还以为要通过指针建立二叉树的方式来实现,觉得挺难的. 其实堆排序实现没有想象中 的那么难. "堆"这个词最初是在堆排序中提出来的,但后来就逐渐指"废料收集储存区",就像程 序设计语言Lisp和Java中所提供的设施那样.我们这里的堆数据结构不是废料收集存储区. 堆排序的 运行时间与归并排序一样为O(n lg n),  但是一种原地(in place)排序. (

虽然久闻大名,但第一次接触算法导论,是看了网易公开课MIT的<算法导论>课,记得 第一集就讲到了 插入排序和归并排序. 几个星期前也买了算法导论这本书,准备慢慢啃~ 这星期主要在看前两 部分,除了对于讲渐进时间.递归式分析这些东西感到云里雾里的,其它的都就 感觉越看越有觉得入 迷,果然不愧是一本经典之作 好吧,开始.本文主要是用C++把书中的算法实现,以及一些笔记. 一.插入排序. 插入算法的设计使用的是增量(incremental)方法:在排好子数组A[1..j- 1]后,将 元素A[ j]

  算法导论上的下标是从1开始的,但是为了和c++ STL的设计思想一致,所有函数的实现统一用左闭右开区间.中间修改了很多次,因为下标修改不是很容易就改掉的,需要始终维持循环不变式,稍微一个步骤出错就会使结果有些错误. #include #include #include #include using namespace std; void merge(int *A, int p, int q, int r) { //merge [p, r),左闭右开区间 int n1 = q - p, n2

做程序的人,都知道了算法的5性--可行性,健壮性,有穷性,高效性,可读性. 这15个字谁都会说了,但是,你是否真正的思考过这个对当今程序界最最重要的用户体验的思考. 过去,我也没多做思考,但是,看了mit的算法导论公开课,我却是觉得一个好的算法, 确实严格遵从算法算法五性. ①可行性--算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成.算法肯定要可行的,不可行的话,是一坨shit,一般可行性是与硬件息息相关.比如,10年前,你要先像现在的搜索引擎一样能够做视搜索,做各种各样的算法

问题描述 算法导论 最大子数组数量问题 进行问题变换后,检查的子数组数量为什么会减少呢. 暴力求解方法有n(n-1)/2 种组合,进行问题变换后为什么有(n-1)(n-2)/2种组合呢,组合的数量应噶事保持不变的啊. 解决方案 http://www.cnblogs.com/chinaxmly/archive/2012/10/10/2718621.html 复杂度降低到O(n)

对于高效算法, 有些比较简单的技术, 如分治法, 随机化, 和递归求解技术. 这边介绍些更为复杂的技术, 动态规划, 贪心算法 当对于复杂问题设计算法时, 首先会想到使用分治法 来解决, 分而治之, 一个很有哲理性的思路, 再复杂的问题都可以不断分解到你可以轻松解决的粒度, 把所有简单问题都解决完后, 组合在一起就得到了复杂问题的解, 可以看出其中典型的递归求解的思路. 使用分治法的要求, 各个子问题是独立 的 (即不包含公共的子子问题,子问题不重叠 ). 如果子问题重叠, 用分治法就比较低效,

问题描述 求问算法导论中一个非常简单的对数问题 求问算法导论中一个非常简单的对数问题.额,各位不要笑话啊. 请问这两个对数是如何推出相等的啊,用的是哪个公式啊? 只记得这个公式了.... 解决方案 解决方案二: begin{align} ln(3^{log_4^n}) & = ln(n^{log_4^3}) log_4^ncdot ln(3) & = log_4^3cdot ln(n) frac{ln(n)}{ln(4)}cdot ln(3) & = frac{ln(3)}{ln(

排序算法总结         从六月初开始看算法导论,陆陆续续看了有2个月了,但实际看的时间只有半个月左右.这期间都忙着找导师.期末考试,同时还回家修养了十来天.真正专心的看算法是在离家返校后,由于没有考试和作业的烦恼,天天都沉浸在算法中,感觉效率较高.这段时间学到的东西较多,下面来总结一下:         学到的排序算法可以分为两类:比较排序.非比较排序.(这些排序算法的详细介绍及c程序实现在本文末都给出了链接,欢迎参考与指正!)         比较排序有:插入排序法.合并排序法.堆排序法

问题描述 我想看算法导论,但是拿着那么厚厚的一本书我就蒙了想问问高手都怎么看这本书的~~~~ 解决方案 解决方案二:慢慢看解决方案三:要学算法,先学好数据结构解决方案四:要参加ACM么?牛叉!解决方案五:看书┗━━━━━练习解决方案六:下学期就要学习数据结构和算法了--看了一小下下,感觉和DM有很多相似哦~~解决方案七:一边看一边练吧,如果要参加ACM的话要搞的很熟,一般情况的话把基本的数据结构和常用算法搞熟就行了,对将来编写高效率,高质量的代码有好处解决方案八:先学数据结构,然后一边看这本书,

Stack, Queue Stack是后进先出, LIFO, 队列为先进先出, FIFO 在python中两者, 都可以简单的用list实现, 进, 用append() 出, Stack用pop(), Queue用pop(0), pop的时候注意判断len(l)  对于优先队列, 要用到前面讲到的堆 链表和多重数组 这些数据结构在python中就没有存在的价值, 用list都能轻松实现 散列表 为了满足实时查询的需求而产生的数据结构, 查询复杂度的期望是O(1), 最差为O(n) 问题描述, 对