

首页  思维导图  详情



CLRS

2019-02-22 17:25:10   0  举报





仅支持查看

AI智能生成

clrs

模版推荐

作者其他创作

大纲/内容

第一章

介绍

第二章

插入排序 O(n2)

归并排序 O(nlogn)

第三章

记号，O, Ω，θ

第四章

分治思想

复杂度 n=1时，T(n) = Θ(1); n>1时，T(n)=2T(n/2)+D(n)。

递归式求解

第五章

概率分析和随机算法

第六章

堆排序

MAX_HEAP  O(h) = O(logn)

BUILD_MAX_HEAP O(nlogn)

HEAPSORT O(nlogn)

BUILD_MAX_HEAP(A) for   exchangeA[1] and A[i]   heapSize--   MAX_HEAP

优先队列

最大堆

操作系统调度，CPU执行优先级最高的任务

接口

INSERT

MAXIMUN

EXTRACT_MAX

INCREASE_KEY

最小堆

事件驱动系统，基于时间

第七章

快排

不稳定

O（nlogn）最坏情况O（n2）

归并

稳定

O（nlogn）

插入

稳定

O（n2）最好情况O（n）

Arrays.sort

数组长度小于47使用插入排序或成对插入排序， 47-287用快排， 287以上，先检查有序性，若大于67个段是无序的就用快排，否则归并。

第八章

线性时间排序

计数排序

O（n）

基数排序

桶排序

第九章

中位数与顺序统计量

RANDOM_SELECT

期望O（N），最坏O（n2）

第十章

基本数据结构

栈

队列

链表

对象和指针

数据机构的接口

CRUD

PREDECESSOR（S,x）

SUCESSOR（S，x）

第十一章

哈希表

直接寻址法（线性函数）

冲突，拉链法

第十二章

二叉搜索树

接口

最坏就是O（logn）

第十三章

红黑树

插入，删除，查询

O（logn）

第十四章

数据结构的扩张

基础数据结构附加信息

第十五章

动态规划

最优子结构：问题的最优解由相关子问题的最优解组合而成

第十六章

贪心算法

每一步都选择最优的取法，和动态规划的区别在于： 每一步只取相关子问题的最优解中最优的一个。

第十七章

摊还分析

分析n次操作平均复杂度的算法

动态表的扩张和收缩

第十八章

B树

阶数t表示节点最大容纳关键词的数量，每个节点都包含卫星数据。

B+数

只有叶子节点才包含卫星数据

增/删时，B树的分裂/合并

O（tlogt(n)）

trie树(前缀树)

第十九章

斐波那契堆

性能高于二项堆





0 条评论

下一页