算法导论第四天学习笔记

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法导论第四天学习笔记，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1137字，纯文字阅读大概需要2分钟。

内容图文

算法导论第四天学习笔记

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

概率分析和随机算法

雇佣问题

//伪代码
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, n3)
	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)

内容总结

以上是互联网集市为您收集整理的算法导论第四天学习笔记全部内容，希望文章能够帮你解决算法导论第四天学习笔记所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---