-
CLRS10 基本数据结构
介绍本章讨论如何通过使用指针的简单数据结构来表示动态集合。这里介绍栈、队列、链表和有根树。10.1 栈和队列 栈: LIFOSTACK-EMPTY(S) return S.top == 0PUSH(S, x) S.top += 1 S[S.top] = xPOP(S) if STACK-EMPTY(S) error "underflow" else S.top -= 1 return S[S.top + 1] 队列: FIFOE...…
-
CLRS9 中位数和顺序统计量
介绍第i个顺序统计量是集合中第i小的元素。9.1 最小值和最大值MINIMUM(A) min = A[1] for i = 2 to A.length if min > A[i] min = A[i] return min需要n-1次比较。MINIMUM-AND-MAXIMUM(A) if len(A) % 2 == 0 if A[1] > A[2] min = A[2] ...…
-
SICP2 Building Abstractions with Objects
介绍Chapter 2: Building Abstractions with ObjectsIntroduction Higher-order functions enhance the power of our language by enabling us to manipulate, and thereby to reason, in terms of general methods of computation. This is much of the essence ...…
-
CLRS8 线性时间排序
介绍讨论三种线性时间复杂度的排序算法：计数排序、基数排序和桶排序。8.1 排序算法的下界 比较排序的下界是Ω(nlgn) 在一个比较排序算法中，我们只使用元素间的比较来获得输入序列中的元素间次序的信息。 在最坏情况下，任何比较排序算法都需要做Ω(nlgn)次比较。因为有n!个叶节点。 堆排序和归并排序都是渐进最优的比较排序算法。 练习8.1-1 What is the smallest possible depth of a...…
-
CLRS7 快速排序
介绍快速排序虽然最坏时间复杂度是O(n^2),但通常是实际排序应用中最好的选择。它的期望时间复杂度是θ(nlgn)，而且其中隐含的常数因子非常小，它还能进行原址排序。7.1 快速排序的描述。QUICKSORT(A, p, r) if p < r q = PARTITION(A, p, r) QUICKSORT(A, p, q-1) QUICKSORT(A, q+1, r)QUICKSORT(A, 1, A.length)PARTITIO...…
-
CLRS6 堆排序
6.1 堆 堆排序的时间复杂度是O(nlgn),且是原址排序。 0 <= A.heap-size <= A.length PARENT(i) return i//2LEFT(i) return 2iright(i) return 2i+1在堆排序的好的实现中，这三个函数通常是以"宏"或者"内联函数"的方式实现的。 最大堆 A[PARENT(i)] >= A[i] 最小堆 A[PARENT(i)] <...…
-
CLRS5 概率分析和随机算法
随机与期望运行时间 当输入是随机时，称运行时间为平均运行时间。 当算法本身做出随机选择时，称随机算法的运行时间为期望运行时间。5.1 雇用问题 练习5.1-1 Show that the assumption that we are always able to determine which candidate is best in line 4 of procedure HIRE-ASSISTANT implies that we know a total order on th...…
-
CLRS4 分治策略
介绍CLRS学习第三=四章，分治策略~4.1 最大子数组问题 分治法解最大子数组FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high) left-sum = -INFINITE sum = 0 for i = mid down to low sum = sum + A[i] if sum > left-sum left-sum = sum max-left ...…
-
CLRS2 算法基础
介绍这是算法导论的第二章~2.1 插入排序 INSERTION-SORT(A) ：for j = 2 to A.length key = A[j] i = j - 1 while i > 0 and A[i] > key A[i+1] = A[i] i = i - 1 A[i + 1] = key正确性： 循环不变式：在for循环每次迭代的开始，A[1..j-1]已排好序。 初始化：当j=2，显然成立。 保...…
-
SICP1 Building Abstractions with Functions
介绍我会在这系列文章里记录学习SICP(Python版)的体会~The Elements of Programming A programming language is more than just a means for instructing a computer to perform tasks. The language also serves as a framework within which we organize our ideas about process...…
-
CLRS1 算法在计算中的应用
介绍在CLRS系列的文章里，我会记录学习算导这本书的收获，并整理习题~1.1 算法 练习1.1-1 给出现实生活中需要排序的一个例子或者现实生活中需要计算凸壳的一个例子。 排序：听歌时将歌曲按字典排序，方便查找。凸壳：平面上有n点，其中没有三个点是共线的，求包含这些点的面积最小的n边形 练习1.1-2 除速度外，在真实环境中还可能使用哪些其它有关效率的量度？ 资源占用 练习1.1-3 选择一种你以前已知的数据结构，并讨论其优势和局限. 链表。...…
-
Hello World
Hi, 今天终于搭建好了自己的博客。其实一直想把做过的事情记录下来，却一直没有找到合适的空间。有了博客就不存在这个问题啦，以后就在这里写下心情和学习经历吧，欢迎关注~…
