1：算法复杂度

时间复杂度：

复杂度=计算次数，不是时间

时间复杂度是：求导，主要看的是时间曲线。要描述的是随着问题规模增大，算法执行时间的增长快慢。

O是估算。O(1)就是常数，没有O(2)。

多项式复杂度与非多项式复杂度

多项式：

a*x^n+bx^n-1....+c ,变量是x,其他都是常量，就叫做x最高位为n的多项式(一元（x未知）n（n是常数）次多项式）。x可以不断增加（x是问题规模，n是常量）。当x无限增长是，其计算规模是线性的，不会呈现指数级别的增长，这样就是可计算的。

复杂度就是取多项式里去变量的最高位

比如这个计算时间函数=n^2+10n+100，则时间复杂度就是O(n^2)

问题分类

P,NP,NPhard问题

P:在多项式时间复杂度内可求出问题解的问题就是P类问题

NP:在多项式时间复杂度内可验证答案是否正确（旅行商问题），求解不一定。

比如计算数独问题：是NP问题，可以在2N次计算内验证答案，求解不一定。

P类问题是NP问题的子集（多项式时间可求解，自然能在多项式时间内验证）。

NP=P？ 数学家还在争论，可以认为NP问题包括P与不确定求解是否符合P，但验证可以在多项式内解决的两类问题。

NP-hard（难题）:比np更复杂，所有NP问题都可以约化为这个问题（数学定义，还没找到）

完全NP:是NP,也是NP-hard(两者的交集）（数学定义，还没找到）

参考：https://zhuanlan.zhihu.com/p/73953567



时间复杂度比较：

常量<线性<多项式<指数级

O(1)＜O(logn)＜O(n)＜O(nlogn)＜O(n2n2)＜O(n3n3)＜O(2n2n)＜O(n!)-https://blog.csdn.net/wtysos11/article/details/52737405



空间复杂度：

算法运行中临时占用的存储空间度量

O(n) 表示需要存储n个 

2：数据结构

常用数据结构（牢记特性与原理）

数组：随机查找--O(1),插入删除O(n)

链表：随机查找--O(n),插入删除O(1)

哈希表：查增删-O(1),哈希表的哈希冲突包括：哈希值冲突 或哈希取模后冲突。

数组与链表都称为线性表

栈：后入先出，典型线程的堆栈，放入一个个栈帧。

队列：先进先出，场景：生产消费，阻塞等待。

树：

二叉树：

二叉排序树:可能不平衡

平衡二叉树：

从任何节点的左右子树高度差不超过1

               插入时如果不平衡，旋转一下就行（左旋，右旋）。

               删除麻烦：需要维护从被删节点到根节点的平衡性

               查找复杂度：O(logN),删除O(logN),添加O(1)

红黑（排序）树：

             概念：节点-黑色，红色，不出现连续红色，每个节点到其下叶子节点的各条路径上黑色节点数相同。TreeMap使用。

特点：近似平衡,增删复杂度O(1),最多3次，查找O(logN)

跳表：

多级别抽取建立上层链表。空间复杂度大，多了辅助节点。

增删查复杂度：O(logn)

3：常用算法



算法归类

穷举算法：尝试所有方法，复杂度O(N!)。

比如：旅行商求解算法

递归算法：

问题：快速排序。

N*(logN),

贪心算法：

问题：背包问题，最短路径

                 方法：每一步都选择当前的最优解。

                  结论：最后结果不是最优，是较优。实现快。

复杂度：O(n),遍历。

改进贪心算法：迪杰斯特拉（最快路径）算法

                     解决问题：有权图中最短路径问题

                     方法： 核心思想： 找到起点到每个节点的最快路径。

                     实现：逐层更新节点的邻居节点（更新起点到其的路径距离）。重复，直到每个节点都算过

了。相当于将问题拆分为小问题，问题不断扩大，扩大时用已经有的解的空间（多个解），去贪心更大范围的解（新加入解空间的每个解是当前范围的最优解）。

                    复杂度：O(n^2)        

动态规划：

                     解决问题： 背包问题

                     寻找合适角度，将求解目标在某（几）各维度上展开，大问题拆分为多个小问题，每个小问题求最优解，寻找大问题的最优解。

                     理解：小偷背包问题。将重量分解1-4，设备逐个添加。

复杂度：O(n^2)