danix800
- 浏览: 30394 次
- 性别:
- 来自: 南京
-
最新评论
文章列表
我给应用【微博数据分析师】打了5分 http://dev.t.qq.com/development/appinfo/801193466
爬虫收集微博数据
#应用推荐#向大家推荐应用：微博爬虫测试http://t.163.com/app/detail/jrn4e9LjHX1l5gqQ
hbase-indexed (HBaseIdx)
HBase secondary index using coprocessors
There are several projects providing secondary index for HBase. This is just one of them.
The HBase community has been talking about secondary index using coprocessors for a period of time, but no much progress has been made. This p ...
Order statistics
Problem: Given n elements in an array, find the kth smallest element (rank k).
The naive algorithm to solve this problem: sort the array A and return A[k]. If use heap sort or merge sort, requires Theta(nlgn) time.
We can do better than this: in linear time.
The trivial ...
How fast can we sort? (Depends on the sorting model: what you can do with the elements)
Comparison sorts: only use comparisons to determine relative order of elements:
quicksort - Theta(nlgn) randomized version
heapsort - Theta(nlgn)
merge sort - Theta(nlgn)
insertion sort - Theta(n^2)
...
在给出快速排序另一种分析之前，先记一下Lecture 4中用到的那个不等式证明的大致框架：
关键点有两个，一是函数xlgx (x>=1)是个凸函数(convex function)。另一点就是将和式分成两部分，一部分k=2，3，...，ceiling(n/2) - 1，另一部分k=ceiling(n/2)，ceiling(n/2)+1，...，n-1。xlgx是凸的可以验证一下它的二阶导数：(xlgx)" = 1/xln2 > 0。由这个凸性可以将每一个klgk约束在对应部分的两个端点所连的直线下面。如果画出函数xlgx的图像这一点会很清楚。剩下的就是计算，会用 ...
第四课80多分钟，好长啊...内容很多，但是Leiserson教授讲得既快又好！
快速排序（Quicksort）是C. A. R. Hoare于1960年发明，当时他正在莫斯科大学（Soviet Union, 前苏联吧）作访问学生。在一个国家物理实验室的机器翻译项目里，为 ...
Lecture 3真得很重要，因为Divide and Conquer思想很重要。本课又是Erik主讲。听了70多分钟，写了6页的Notes，现在整理一下。
分治（Divide and conquer, or divide et impera）
分治法是非常基本但却很强大的算法设计技巧。这也是这个课程 ...
这个Lecture包括了CLRS中的Chapter3-Chapter4两章内容：渐近性标记和解递归。Erik Demaine主讲。Gee! 每次看到Erik的一头“秀发”跟Leiserson教授的光头就想笑笑，别误会，Erik's a man...
解递归
解递归常用的有三种方法：替换法（Substitution method），递归树法（Recursion tree），主方法（Master method）。
替换法
Guess the form of the solution.
Verify by induction.
Solve for constants.
...
看完Lecture 1的视频后，感觉听这些教授上课真的是一种享受！随后把Chapter 1, Chapter 2拿出来再复习一下，把一些需要记的东西记下来吧。有些内容正文上没有提到，而是作为练习给出的，所以有必要把一些解法分析什么的写下来。
第一章内容没什么吸引我的地方，随后的Chapter Notes倒是很吸引人（以前没读过这里）。这里提到了不少的大作，都是CS里的大牛啊。
第二章第一部分的插入排序中用到了循环不变量（Loop Invariants）来证明插入排序的正确性。
INSERTION-SORT(A, n) // sorts A[1..n], array ind ...
Introduction to Algorithms, MIT OCW 6.046J, Instructors: Prof. Charles Leiserson and Prof. Erik Demaine.
Charles Leiserson (http://people.csail.mit.edu/cel/)，即Introduction to Algorithms一书的作者CLRS中的L，1975年获得耶鲁大学计算机学士和数学学士学位，1981年于CMU获得Ph.D学位，其导师为Jon Bentley和H.T.Kung (http://en.wikipedia.org/wiki/C ...
势能方法将已预付的工作表示成一种“势能”，在需要的时候可以释放出来，以支付后面的操作。势是与整个数据结构而不是其中的个别对象发生联系的。 开始时，先对一个初始数据结构D_0执行n个操作。对每个i=1，2，...，n，设为第i个操作的实际代价，D_i为对数据结构D_{i-1}作用第i个操作的结果。势函数将每个数据结构D_i映射为一个实数(D_i)。第i个操作的平摊代价根据势函数的定义为
每个操作的平摊代价为其实际代价加上由于该操作所增加的势。n个操作的总的平摊代价为：
如果我们能定义一个势函数使得(D_n) >= (D_0)，则总的平摊代价\sum_{i= ...
平摊分析这一章，CLRS的英文版一直没有读懂，不知道是不是心太浮了。今天把中文版的拿出来再读一读，希望愚钝的头脑能开一开窍。
这一部分总标为高级分析技巧，想来也不是那么好理解的，所以一遍不懂就再来一遍，百遍之内定能见其义了！
在amortized analysis中，执行一系列数据结构操作(push, pop, multipop, etc)所用时间是通过对执行的所有操作（n个这样的操作）求平均得出的。平摊分析可以用来证明在一系列操作中，通过对所有操作求平均之后即使其中单一操作具有较大的代价，平均代价还是很小的。
常用的平摊分析有3种：
聚集分析（Aggregate analysis）。 ...
上午看到一个题目，给定一个二叉搜索树(BST)的前序遍历(PreOrder)序列，给出算法构建原BST，花了几分钟时间想了个递归解(基本思路是分治，Divide & Conquer)，给出了如下的Pseudo Code，用Java实现了一下，算法正确。
BUILD-BST-FROM-SEQ(s, j, r)
l := r - j + 1
if l < 1 then return NIL
root := MAKE-NODE()
key[root] := s[j]
if l = 1 then return root
i := j + 1
while i < ...