（点击上方公众号，可快速关注）
英文：Tsiege
译文： 伯乐在线 - 胡西瓜
网址：http://blog.jobbole.com/90256/
这份清单，既是一份有助于对这些题目做深入研究的快速指南和参考，也算是计算机科学课程中不能忘记的基础知识总结，因此并不可能全面覆盖所有内容。它也可以作为 gist 在 Github 上公开，人人都可以编辑和补充。
一、数据结构基础
数组
定义
按顺序连续存储数据元素，通常索引从0开始 以集合论中的元组为基础 数组是最古老，最常用的数据结构
知识要点
数组长度固定，意味着声明数组时应指明长度
如果动态数组已满，则把每一元素复制到更大的数组中
时间复杂度
O(1)索引：一维数组：O(1)，动态数组：O(1) O(n)查找：一维数组：O(n)，动态数组：O(n) O(log n)最优查找：一维数组：O(log n)，动态数组：O(log n) O(n)插入：一维数组：n/a，动态数组：O(n)
链表
定义
最基础的结点包含一个数据和一个指针（指向另一结点）
要点
为优化插入和删除而设计，但不利于索引和查找 双向链表包含指向前一结点的指针 循环链表是一种终端结点指针域指向头结点的简单链表 堆栈通常由链表实现，不过也可以利用数组实现
堆栈是“后进先出”（LIFO）的数据结构
队列是“先进先出”（FIFO）的数据结构
时间复杂度
哈希表或哈希图
定义
这一过程称为散列（hashing），是输入与输出一一对应的概念
要点
所有的哈希函数都存在这个问题
用一个非常大的哈希表，可以有效缓解这一问题 哈希表对于关联数组和数据库检索十分重要
时间复杂度
O(1)索引：哈希表：O(1) O(1)查找：哈希表：O(1) O(1)插入：哈希表：O(1)
二叉树
定义
要点
时间复杂度
索引：二叉查找树：O(log n) 查找：二叉查找树：O(log n) 插入：二叉查找树：O(log n)
二、搜索基础
广度优先搜索
定义
要点
当树的宽度大于深度时，该搜索算法较优 进行树的遍历时，使用队列存储树的信息
原因是：使用队列比深度优先搜索更为内存密集 由于需要存储指针，队列需要占用更多内存
时间复杂度
深度优先搜索
定义
从左边开始一直往下遍历树的结点，直到不能继续这一操作 一旦到达某一分支的最末端，将返回上一结点并遍历该分支的右子结点，如果可以将从左往右遍历子结点 当前这一分支搜索完毕后，转入根节点的右子结点，然后不断遍历左子节点，直到到达最底端 最右的结点是最末结点（即所有祖先中最右的结点）
要点
当树的深度大于宽度时，该搜索算法较优 利用堆栈将结点压栈
时间复杂度
广度优先搜索 VS. 深度优先搜索
就宽度而言，较浅的树适用广度优先搜索 就深度而言，较窄的树适用深度优先搜索
细微的区别
三、高效排序基础
归并排序
定义
要点
时间复杂度
O(n)最好的情况：归并排序：O(n) 平均情况：归并排序：O(n log n) 最坏的情况：归并排序：O(n log n)
快速排序
定义
要点
时间复杂度
冒泡排序
定义
| 
注册
登录
