矩阵链乘最少时间问题——动态规划

问题描述参见《算法导论》动态规划一章。
思路:该问题可以分解成两个子问题,当A[i]*A[i+1]*……*A[n]代价最小时,去掉最外面的括号,这时算式有两部分组成:A[i]*……A[k] A[k+1]*A[k+2]*……*A[n]
同样的,可以递归地解决这两个子问题:分别再分割
但是因为不清楚k是多少时m[i][j]最小,所以要求出所有的k(k>=i && k<=j-1),去最小值

O(n)时间快速选择

如何在期望线性时间选出第i小的元素?
通过该调用快速排序的random_partition可以实现在平均O(n)时间内选出第i小的元素。
根本原因:这种方法实际上是对数组进行了局部的排序,每次只排序partition后的一半,因为将快速排序的平均时间O(nlogn)降到了O(n).严谨的数学证明请参见《算法导论》。
下面先给出算法的实现,然后叙述缺点及改进。

算法导论——(二叉)堆和堆排序

这篇笔记不知道该发在acm还是数据结构,就数据结构吧。。
今天数电课还是挺有收获的,至少认识到3个知识点:1、原来一直认为单片机是早期的cpu,现在才知道整个单片机应当是mcu(微控制单元,以前一直以为mcu==cpu),而cpu是mcu的核心;2、单片机的RAM是SRAM,呵呵,原来是cache,怪不得这么快。。3.位异或可以看成单个位之间的相加,第一次听到这种理解,颇有醍醐灌顶之感。
好吧,还是来说说正题,关于堆.
1.(二叉)堆是完全二叉树
2.堆的高度:从下往上(最下面一层高度为0)(从0开始)。
3.高度与
4.约定:用一维数组存储堆,根是heap[1]
5.高度h和元素个数n的关系:h=floor(log(n))
6.如何将无序数组建成大根堆:对非叶子节点从下往上保持堆一遍
7.实现《算法导论》中的伪代码