算法导论笔记 - 高级数据结构

B树 指针 磁盘 算法 红黑树

B树

  • B树类似于红黑树。他们在降低磁盘I/O操作数方面更好一些。因为B树的分支因子可以非常大,所以其高度要比红黑树小得多。
  • B树是以一种自然的方式推广了的二叉搜索树。

B树的定义

我们假定,任何与 关键字相联系的 卫星数据将与关键字一样存放在同一结点中,并随着关键字一起移动。一棵B树T是具有以下性质的有根树(根为T.root):

B+树是B树的变种。

  1. 每个结点x有如下属性: a. x.n,表示结点x中的关键字个数 b. x.n个关键字以非降序排列 c. x.leaf,表示x是否为叶结点
  2. 每个内部结点包含 x.n+1 个指针指向孩子们 c[i]
  3. x 中的关键字 x.key[i] 对子树中的关键字 k[i] 进行分割,n个关键字,n+1个子树
  4. 每个叶结点有相同的深度,即树的高度h
  5. 每个结点的关键字数由 最小度数(minimum degree)t>=2控制: a. 除根节点外,每个结点至少含 t-1 个关键字 b. 每个结点至多含 2t-1 个关键字

如果 n>=1,那么对任意一棵包含n个关键字、高度为h、最小度数t>=2 的B树T,有 $h\leq \log_t \frac{n+1}{2}$

算法导论笔记 - 高级设计和分析技术

分治 常量 排序 数组 算法 贪心 队列 二叉树 动态规划 字符编码 矩阵连乘 哈夫曼编码 最优二叉搜索树 最长公共子序列

动态规划

动态规划方法通常用来求解 最优化问题(optimization problem),通常有四个步骤:

  1. 刻画一个最优解的特征
  2. 递归地定义最优解的值
  3. 计算最优解的值
  4. 利用计算出的信息构造一个最优解

动态规划(dynamic programming)与分治方法相似,都是通过组合子问题的解来求解原问题。区别在于分治法的子问题互不相交,而动态规划应用于子问题重叠的情况。

算法导论笔记 - 排序和顺序统计量

排序 数组 算法 队列 二叉树

  • 待排序的项称为 记录(record),每个记录包含一个 关键字(key),即排序问题中要重排的值,记录的剩余部分由 卫星数据(statellite data)组成。
  • 如果输入数组中仅有常数个元素需要在排序过程中存储在数组之外,则称排序算法是 原址的(in place)。插入排序可以在$\Theta(n^2)$时间内将n个数排好序,是一种非常快的原址排序算法;归并排序有更好的渐近运行时间$\Theta(n\lg n)$,但它使用的MERGE过程并不是原址的。
算法 最坏情况运行时间 平均情况/期望运行时间
插入排序 $\Theta(n^2)$ $\Theta(n^2)$
归并排序 $\Theta(n\lg n)$ $\Theta(n\lg n)$
堆排序 $O(n\lg n)$
快速排序 $\Theta(n^2)$ $\Theta(n\lg n)$(期望)
计数排序 $\Theta(k+n)$ $\Theta(k+n)$
基数排序 $\Theta(d(n+k))$ $\Theta(d(n+k))$
桶排序 $\Theta(n^2)$ $\Theta(n)$(平均情况)

算法导论笔记 - 基础知识

分治 排序 数组 算法 归并排序 插入排序

算法基础

插入排序

//INSERTION-SORT(A)
for j = 2 to A.length
	key = A[j]
	//Insert A[j] into the sorted sequence A[1..j-1]
	i = j - 1 
	while i > 0 and A[i] > key
		A[i + 1] = A[i]
		i = i - 1
	A[i+1] = key
  • 循环不变式:初始化、保持、终止

##分析算法

  • 单处理器计算模型:随机访问机(random-access machine,RAM):算数指令、数据移动指令、控制指令。
  • 最坏情况、平均情况、增长量级

Computer Organization and Design 笔记 - Multicores, Multiprocessors, and Clusters

操作系统 多处理器 并行 线程

Introduction

multiprocessor

A computer system with at least two processors. This is in contrast to a uniprocessor , which has one.

job-level parallelism or process-level parallelism

Utilizing multiple processors by running independent programs simultaneously.

parallel processing program

A single program that runs on multiple processors simultaneously.

cluster

A set of compters connected over a local area network (LAN) that functions as a single large message-passing multiprocessor.

multicore microprocessor

A microprocessor containing multiple processors (“cores”) in a single integrated circuit.

para-cate@1.5x

Computer Organization and Design 笔记 - Storage and Other I/O Topics

操作系统 RAID

Introduction

io-dev@1.5x

Dependability, Reliability, and Availability

Dependability is the quality of delivered service such that reliance can justifiably be placed on this service.

Reliability is a measure of the continuous service accomplishment(or, equivalently, of the time to failure) from a reference point.

mean time to failure(MTTF) is a reliability measure. annual failure rate(AFR) is the percentage of devices that would be expected to fail in a year for a given MTTF. Service interruption is measured as mean time to repair(MTTR). Mean time between failures(MTBF) is simply the sum of MTTF and MTTR.

Availability is a measure of service accomplishment with respect to the alternation between the two states of accomplishment and interruption.

Availability = MTTF / MTBF

3 ways to improve MTTF:

  1. Fault avoidance: preventing fault occurrence by construction.
  2. Fault tolerance: using redundancy to allow the service to comply with the service specification despite faults occurring, which applies primarily to hardware faults.
  3. Fault forecasting: predicting the presence and creation of faults, which applies to hardware and software faults, allowing the component to be replaced before it fails.

导航: 上一页 下一页

🔝