概念
1，算法：解决问题的思路与方法。
2，数据结构：为了算法更好的处理问题而总结定义的一组数据规则。
- 物理结构：数据在磁盘上的存储结构,分为连续存储与非连续存储。对应的逻辑结构：数组与链表。
- 逻辑结构：针对常见问题归纳定义的一套数据规则。常见的：数组，链表，栈，队列，散列表，跳表，二叉树，图。最终对应到磁盘或内存中只有连续与非连续存储。
3，算法设计的标准：在最短的时间内使用最少的资源获取一个准确的结果
- 有穷性，确定性，可行性。比如：循环必须有结束条件，每一步不能出现歧义。最终结果保证准确。
- 算法尽量保证可读性，便于阅读与交流。
- 代码健壮，需要考虑边界条件与特殊情况，每一种场景都需要闭环处理。
- 高效率：对应算法的执行速度快，可以参考时间复杂度进行定量的判断。
- 低内存：执行算法运行需要的内存尽量少，可以参考空间复杂度度进行判断。
算法复杂度分析
1，在设计算法时必须考虑准确性 ，而效率与空间有时需要根据数据规模，设备性能等综合考虑，最优解可能不是效率最高，内存最小的。其中需要考虑空间换时间或时间换空间的策略。此时需要通过对算法的复杂度进行分析获取最优解。
2，算法的复杂度只能初步估算算法的执行效率，而不能代码算法的真实执行效率。一般数据量越大，越接近分析的趋势。表示方式：大O复杂度表示法。
时间复杂度
用于判断算法的执行效率，表示代码执行的时间随数据规模增长的变化趋势。针对单一设置场景可以通过模拟打印执行时间进行统计比较。
分析方法：
1，统计代码执行的次数时，默认不同的操作执行时间相同(比如：a+b 与 ab 默认都是统计一次，实际加法的执行效率更高)。
2，多段代码执行时只关心循环次数最多代码的复杂度。即总复杂度等于量级最大代码段的复杂度，遵循加法原则。
3，复杂度分析时忽略常量的影响，前提条件是数据规模n相对很大。比如f(n) = 20n^2 +1000，当n非常大时，复杂度表示为：O(n) = n^2。而当n较小时，比如n=5，此时常量不能省略，需要参与多种算法性能的比较。
4，嵌套代码的复杂度 = 多层代码复杂度的乘积，遵循乘法原则。
常见的复杂度
1，常量级别：O(1)：代表算法执行的次数固定，不随数据规模增长。
//获取平方和代码执行的次数为3，但时间复杂度表示O(1)而不是O(3)
public int square(int a, int b) {
a *= a;
b *= b;
return a + b;
}
2，对数级别：O(logn)，O(nlogn)：常见的场景：二分查找的时间复杂度logn。归并排序的时间复杂度nlongn
//二分查找的前提时：数组datas有序。此时最多执行次数logn，以2为底数。根据乘法原则，外层加个循环调用，时间复杂度为O(nlogn)。
public int find(int[] datas, int num) {
int index = -1;
int start = 0;
int end = datas.length - 1;
if (datas[start] > num || datas[end] < num) {
return index;
}
while (start <= end) {
int middle = ((end - start) >> 1) + start;
if (datas[middle] == num) {
return middle;
} else if (datas[middle] < num) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return index;
}
3，多次级别：O(n2)，O(n3)等。一般场景为多个循环嵌套，遵循乘法原则。常见的有冒泡排序
//双层for循环，执行次数为n^2。时间复杂度O(n^2)
public void sort(int[] datas) {
int n = datas.length;
if (n < 2) {
return;
}
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (datas[i] > datas[j]) {
int tem = datas[i];
datas[i] = datas[j];
}
}
}
}
4，NP级别(时间复杂度为非多项式量级的算法问题叫做NP问题)：O(n！)，O(2^n)。特点是随着n的增大执行时间会急剧增加。一般使用暴力枚举产生的，可以考虑使用动态规划，贪心等进行优化。常见的：n个字符串找最长相同的字符串，n个物品选中与不选。
//执行次数：(n-1)*(n-2)*(n-3)*...*(2)*。字符串比较不考虑长度，默认当做一次。此时时间复杂度为O(n！)
public String findSame(String[] datas) {
int n = datas.length;
String result = "";
for (int i = 0; i < n - 1; i++) {
String tem = datas[i];
if (find(tem, i + 1, datas)) {
if (result.length() < tem.length()) {
result = tem;
}
}
}
return result;
}
private boolean find(String str, int start, String[] datas) {
int n = datas.length;
for (int i = start; i < n; i++) {
if (str.equals(datas[i])) {
return true;
}
}
return false;
}
5，通常时间复杂度排序：O(1)常数阶 < O(log n)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n) 指数阶。在leetcode中根据算法的复杂度和数据规模，一般执行次数超过10^7会出现算法超时，此时应该优化算法使时间复杂度的级别更小。
复杂度分类：
1，最好情况时间复杂度：在理想情况下，执行代码的时间复杂度。比如使用break，return等打断循环时，如果执行结果在index=0的位置时，此时时间复杂度为：O(1)
2，最坏情况时间复杂度：在最坏的情况下，执行代码的时间复杂度。
3，平均情况时间复杂度：综合考虑最好，最坏情况以及出现的概率，计算时间复杂度的平均值。
4，均摊时间复杂度：通过对最坏情况时间复杂度进行分摊的方式，快速分析平均时间复杂度的方法。
//无序数组中查找元素。最好时间复杂度：O(1)，最坏时间复杂度：O(n)，平均时间复杂度：O(n)
//平均次数：((1+2+3+....n-1) + n*(n-1))/n
public int find(int[] datas, int num) {
int n = datas.length;
for (int i = 0; i < n; i++) {
if (datas[i] == num) {
return i;
}
}
return -1;
}
//数组赋值时，大部分时间复杂度为：O(1)，遇到扩容时复杂度为：O(n)。根据出现的频率，将扩容均摊到每次的赋值中，时间复杂度为：O(1)
private int[] datas = new int[16];
private int size = 16;
private int count = 0;
public void add(int num) {
if (count < size) {
datas[count] = num;
} else {
//数组扩容
size <<= 1;
int[] tem = Arrays.copyOf(datas, size);
datas = tem;
datas[count] = num;
}
count++;
}
空间复杂度
用于估算算法执行过程中占用的空间。与时间复杂度分析方式相同。常见的复杂度：O(1)，O(n)，O(n^2)，O(logn)，O(nlogn)。
- 存储二进制数时，输入的空间复杂度为O(logn)bit。比如：输入8使用二进制表示3个bit，对应输入n使用logn个bit。
对于时间复杂度与空间复杂度不需要追求单一最优解，有时需要增加空间复杂度换区时间复杂度的减小。比如：背包问题使用暴力枚举的方式：空间复杂度：O(1)，时间复杂度为：O(2^n)。使用动态规划进行优化后：空间复杂度：O(n)，时间复杂度为：O(nV)。有时需要增加时间复杂度来减少空间复杂度。比如:图的存储和查找。
常见的数据结构(逻辑结构)
线性结构
1，数组
2，链表
3，栈
4，队列
5，散列表
树
1，二叉树
2，多路查找树
3，堆
图
1，图的存储
2，图的搜索
3，图的排序
常见的算法
常见的排序
1，冒泡排序
2，插入排序
3，选择排序
4，快速排序
5，归并排序
6，堆排序
7，基数排序
8，桶排序
搜索
1，广度优先搜索bfs
2，深度优先搜索dfs
3，A*启发式搜索
查找
1，线性二分查找
