算法导论第四天学习笔记

• 概率分析和随机算法
• 雇佣问题
• 指示器随机变量
• 随机算法
• 随机排列数组
• 排序和顺序统计
• 堆排序
• 堆
• 维护堆的性质
• 建堆

概率分析和随机算法

雇佣问题

//伪代码
HIRE-ASSISTANT(n):
	best = 0;
	for i= 1 to n
		interview candidate i
		if candidate i is better than candidate best
		best = i
		hire  candidate i

指示器随机变量

随机算法

//伪代码
HIRE-ASSISTANT(n):
randomly permute the list of candidates
	best = 0;
	for i= 1 to n
		interview candidate i
		if candidate i is better than candidate best
		best = i
		hire  candidate i

随机排列数组

//伪代码
PERMUTE-BY-SORTING(n):
	n = A.length
	let P[1..n] be a new array
	for i = 1 to n 
		P[i] = RANDOM(1, n³)
	sort A, using P as sort keys

//伪代码
RANDOMIZE-IN-PLACE(A):
	n = A.length
	for i = 1 to n
		swap A[i] with A[RANDOM(i, n)]

排序和顺序统计

堆排序

堆

（二叉）堆是一个数组，可以被看成一个近似的完全二叉树。

维护堆的性质

//伪代码
MAX-HEAPIFY(A, i):
	l = LEFT(i)
	r = RIGHT(i)
	if l <= A.heap-size and A[l] > A[i]
		largest = l
	else largest = i
	if r <= A.heap-size and A[r] > A[largest]
		largest = r
	if larget != i
		exchange A[i] with A[largest]
		MAX-HEAPIFY(A, largest)

建堆

BUILD-MAX-HEAP(A):
	A.heap-size = A.length
	for i = ⌊A.length / 2⌋ downto 1
		MAX-HEAPIFY(A, i)