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)。
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
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个段是无序的就用快排，否则归并。
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 条评论
下一页
为你推荐
查看更多
抱歉，暂无相关内容 
