data-structures-and-algorithms

介绍

java数据结构

1.时间复杂度和空间复杂度 1.时间复杂度计算方法
1)事后统计法:直接比较程序运行前后的时间差
2)事前估算法: T(N) = O(f(n)) --> T(N) = O(n^2)
分析思路:
(1):用常数1代替所有加法常数 常数  T(n)=n²+7n+6 => T(n)=n²+7n+1
(2):修改后的运行次数函数中，只保留最高阶项  T(n)=n²+7n+1 => T(n) = n²
(3):去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²)
3)常见的时间复杂度:
常数阶O(1)
对数阶O(log2n)
线性阶O(n)
线性对数阶O(nlog2n)
平方阶O(n^2)
立方阶O(n^3)
k次方阶O(n^k)
指数阶O(2^n)
4)常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) ， 随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越
5)我们应该尽可能避免使用指数阶的算法
6)在可能的情况下，使用空间换时间的概念进行优化（例如使用缓存等）
2.列表（数组）

3.链表
1.单链表

2.双链表  

4.队列:队尾添加数据,队头取出数据
1.用数组实现队列

2.用数组实现循环队列  

5.栈

6.优先队列/堆

7.哈希表
1.碰撞解决方法:
1)开放地址法
2)链地址法
3)再次哈希法
4)建立公公溢出区
2.布隆过滤器

8.树
1.二叉树(各种遍历)
2.AVL树
3.B树与B+树
4.红黑树
5.红段树

9.常见算法
1.十大排序算法
1)简单排序:选择/插入/冒泡(必学)
2)分治排序:快速排序/归并排序(必学)
3)分配排序:桶排序/基数排序
4)树状排序:堆排序(必学)
5)其他:计数排序(必学)/希尔排序
2.图论算法
1)图的表示:邻接矩阵和邻接表
2)遍历算法:深度搜索和广度搜索(必学)
3)最短路劲算法:Floyd,Dijkstra(必学)
4)最小生成树算法:Prim,Kruskal(必学)
5)实际常用算法
6)二分图匹配
7)拓展:中心性算法,社区发现算法