算法虐我千百遍，我待算法如初恋

把所有经典算法、数据结构手搓一遍
理解源码 STL源码，各种库，推荐使用cppreference、cplusplus 。
看经典书籍（《C++ Primer中文版》、《Essential C++》、《More Effective C++（中文版）》、《提高C++性能的编程技术》、《C++ Templates中文版》、《STL源码剖析》等等）
刷题 (主刷leetcode)

时间复杂度

$O (1) < O (l o g_{2} n) < O (n) < O (\sqrt{n}) < O (n l o g_{2}^{n}) < O (n^{c}) < O (c^{n}) < O (n!) < O (n^{n})$

算法设计思想

算法

基本概念

算法的五个特征

有穷性：有限步之后结束
确定性：不存在二义性，即没有歧义
可行性：比如受限于计算机的计算能力，有些算法虽然理论上可行，但实际上无法完成。
输入：能被计算机处理的各种类型数据，如数字，音频，图像等等。
输出：一至多个程序输出结果。

复杂度

时间复杂度：
- 它用来衡量算法随着问题规模增大，算法执行时间增长的快慢；
- 描述问题规模的函数： $T (n)$ 是时间规模函数时间复杂度主要分析 $T (n)$ 的数量级
- $T (n) = O (f (n))$ ， $f (n)$ 是算法中基本运算的频度一般我们考虑最坏情况下的时间复杂度
空间复杂度：
- 它用来衡量算法随着问题规模增大，算法所需空间的快慢；
- 是问题规模的函数： $S (n) = O (g (n))$ ，算法所需空间的增长率和 $g (n)$ 的增长率相同。

复杂度计算

常用的时间复杂度大小关系：
复杂度如何计算
- 时间复杂度计算（单个循环体）
  - 直接关注循环体的执行次数，设为k
- 时间复杂度计算（多个循环体）
  - 两个运算规则：乘法规则，加法规则。

基础数据结构&算法示例

Linear List & Array

遍历、元素统计、改变移动、旋转轮换

二维数组、滚动数组

前缀和数组 & 差分数组

规定一维，原数组 $a_{n}$ 、前缀和数组 $p r e f i x_s u m_{n + 1}$ 、差分数组 $d i f f e n c e_{n + 1}$

由前缀和数组定义可知 $p r e f i x_s u m [i] = p r e f i x [i - 1] + a [i]$ （其中 $p r e f i x_s u m [0] = 0$ ）

由差分数组定义可知 $d i f f e n c e [i] = a [i] - a [i - 1]$ （其中 $d i f f e n c e [0] = a [0]$ ）

对前缀和数组，做一次差分即得原数组，反之亦然。

用邮票贴满网格图

Linked List

自定链表数据结构

链表的旋转、合并

Queue

Stack

Tree

二叉树
- 快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历
二叉查找树BST 有序的二叉树，中序遍历结果是递增的
平衡二叉树 AVL树绝对平衡二叉树；
红黑树弱平衡二叉树；使用广泛
B树
B+树 mysql 索引使用 B+树的数据结构
字典树trie 字典树也叫前缀树，单词查找树
二叉堆
伸展树
后缀树
- Ukkonen's Algorithm （动画演示）
- McCreight's Algorithm
斐波那契堆(Fibonacci Heap)
最优二叉树（哈夫曼树）
- 哈夫曼编码

String

字符串
子串查找
- BF算法
- KMP算法
- BM算法
正则表达式
数据压缩
排序

Map

图的存储结构和基本操作（建立，遍历，删除节点，添加节点）
最小生成树
拓扑排序
关键路径
最短路径: Floyd,Dijkstra,bellman-ford,spfa

Sort

Search

哈希表： O(1) hashtab<实现参考这里
散列函数
碰撞解决
有序表查找：二分查找
顺序表查找：顺序查找, 复杂度O(N)
分块查找：块内无序，块之间有序；可以先二分查找定位到块，然后再到块中顺序查找
动态查找: 二叉排序树，AVL树，B- ，B+（这里之所以叫动态查找表，是因为表结构是查找的过程中动态生成的）

C++ STL的容器分类

..

container

刷算法题目

字符串
堆和栈
链表
数值问题
数组和数列问题
矩阵问题
二叉树
图
海量数据处理
智力思维训练
系统设计

海量数据处理

Hash映射/分而治之
Bitmap
Bloom filter(布隆过滤器)
Trie树
数据库索引
倒排索引(Inverted Index)
双层桶划分
外排序
simhash算法
分布处理之Mapreduce

开源项目中的算法

YYCache
cocos2d-objc
bitcoin
geohash
kafka
nginx
zookeeper
...

15个经典基础算法

KMP 字符串匹配算法
Hash
快速排序
快速选择SELECT
红黑树（一种弱/自平衡的“二叉查找树”）
BFS/DFS （广度/深度优先遍历）
寻路算法：求解最短路径
Dijkstra：最短路径算法
SPFA(Shortest Path Faster Algorithm) 单元最短路径算法
启发式搜索
遗传算法 GA
DP (动态规划 dynamic programming)
图像特征提取之SIFT 算法 , 广泛的应用于图像识别，图像检索，3D重建等CV的各种领域
傅立叶变换

参考链接和学习网站

July 博客

《数学建模十大经典算法》
《数据挖掘领域十大经典算法》
《十道海量数据处理面试题》
《数字图像处理领域的二十四个经典算法》
《精选微软等公司经典的算法面试100题》
The-Art-Of-Programming-By-July
微软面试100题
程序员编程艺术

基本算法演示

http://www.cs.usfca.edu/~gal<s/visualization/Algorithms.html

编程网站

Leetcode个人主页
AcWing 刷题
codetop 企业高频面试题库，刷题必备
openjudge 开放在线程序评测平台，可以创建自己的OJ小组
九度OJ
这有个ACM训练方案

竞赛网站

Leetcode竞赛
AtCoder 英国网站，作息阴间的可以一试
ForceCd 同上

网课

代码随想录：刷题思路讲解
高级数据结构和算法：北大教授张铭老师在coursera上的课程。完成这门课之时，你将掌握多维数组、广义表、Trie树、AVL树、伸展树等高级数据结构，并结合内排序、外排序、检索、索引有关的算法，高效地解决现实生活中一些比较复杂的应用问题。当然coursera上也还有很多其它算法方面的视频课程。
算法设计与分析 Design and Analysis of Algorithms ：由北大教授Wanling Qu在coursera讲授的一门算法课程。首先介绍一些与算法有关的基础知识，然后阐述经典的算法设计思想和分析技术，主要涉及的算法设计技术是：分治策略、动态规划、贪心法、回溯与分支限界等。每个视频都配有相应的讲义（pdf文件）以便阅读和复习。

其它

OI Wiki 主要内容是 OI/ACM-ICPC 编程竞赛 (competitive programming) 相关的知识整理, 包括基础知识、常见题型、解题思路以及常用工具等内容。

labuladong 的算法小抄作者整理了很多的解题套路框架，看完获益良多

算法设计思想 ​

算法 ​

算法的五个特征 ​

复杂度 ​

复杂度计算 ​

基础数据结构&算法 示例 ​

Linear List & Array ​

遍历、元素统计、改变移动、旋转轮换 ​

二维数组、滚动数组 ​

前缀和数组 & 差分数组 ​

Linked List ​

自定链表数据结构 ​

链表的旋转、合并 ​

Queue ​

Stack ​

Tree ​

String ​

Map ​

Sort ​

Search ​

C++ STL的容器分类 ​

刷算法题目 ​

海量数据处理 ​

开源项目中的算法 ​

15个经典基础算法 ​

推荐阅读 ​

刷题必备 ​

基础 ​

算法设计 ​

延伸阅读 ​

参考链接和学习网站 ​

基本算法演示 ​

编程网站 ​

竞赛网站 ​

网课 ​

其它 ​