数据结构
逻辑结构:集合,线性,树形,图形
物理结构(存储结构);顺序存储,链式存储
算法特性:输入、输出、有穷性、确定性、可行性
常见时间复杂度
常见数据结构的时间复杂度(集合,线性,树,图)
线性表(顺序存储结构、链式存储结构)
顺序存储结构:查找O(1),增加O(n),删除O(n)
链式存储结构(单链表,静态链表,循环链表,双向链表):查找O(n),增加O(1),删除O(1)
栈和队列
栈:顺序栈和链栈的时间复杂度都为O(1),空间上顺序栈要预先分配足够的空间,链栈要存储指针数据,所以都有空间浪费;
顺序队列:普通顺序队列有队列溢出的问题,入队时间复杂度为O(1),出队时间复杂度为O(n),循环顺序队列依然有队列溢出的问题,但是出入队列的时间复杂度都为O(1);
链式队列:出入队列的时间复杂度都为O(1),相对于循环顺序队列的需要一次性分配空间且空间不可变,链式队列在用到的时候才分配空间且空间不受限制。
串
朴素模式匹配:平均时间复杂度:O((n+m)/2),最坏时间复杂度:O((n-m+1)*m)
KMP算法:最坏时间复杂度:O(n+m),当模式与主串存在许多“部分匹配”的情况下较有优势
树
树的存储结构:双亲表示法、孩子表示法、孩子兄弟表示法;
二叉树:斜树、满二叉树、完全二叉树,哈弗曼树
图
图的概念:无向图,有向图,简单图,无向完全图,有向完全图,网,连通图
图的存储:邻接矩阵表、邻接表、十字链表、邻接多重表、边集数组
图的遍历:深度优先遍历、广度优先遍历
最小生成树算法:普里斯、克鲁斯卡尔 http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html 克鲁斯卡尔针对边来展开,变数少的时候效率较高
最短路径:迪杰斯特拉 http://blog.csdn.net/mu399/article/details/50903876、弗洛伊德 http://blog.csdn.net/bjtu_dubing/article/details/50333027
拓扑排序:
关键路径:
查找
顺序表查找:
有序表查找:折半查找、插值查找、斐波那契
线性索引查找:稠密索引,分块索引,排序索引
二叉排序树:
AVL树:
多路查找树(B树):2-3树、2-3-4树、B+树
排序
排序的概念:稳定排序,不稳定排序,内排序、外排序
排序算法:冒泡排序、简单排序,插入排序,希尔排序http://blog.csdn.net/morewindows/article/details/6668714、堆排序,归并排序 http://www.cnblogs.com/chengxiao/p/6194356.html、快速排序
本文转自 古道卿 51CTO博客,原文链接:http://blog.51cto.com/gudaoqing/1954585