常用算法
一、算法是什么？
算法并没有一种固定的定义，我将它看作一种“解决问题的方法”，换言之，对输入的数据进行特定的
处理，从而得到我们需要的结果，这便是算法的作用。
但是，并不是所有解决方法都能称为算法，算法一般都有极强的“类属性”，即对特定类型的问题有着
以不变应万变的解决方式，它更像是一种思路。
我们用最常见的例子来帮助大家理解什么是算法。
比方说，我们现在要求解从1到100的所有自然数的和，我们该如何计算呢？最简单的方法当然是老老实实
的从1开始加，利用循环，逐个相加，即可得到答案，但显然，这个方法虽然思路简单，但并不是很简洁。
代码实现如下，此处需要注意的是，range()函数生成的可遍历范围为左开右闭区间，因此我们右端点
需要选择在101。
sum_a = 0
for i in range(1, 101):
sum_a += i
print(sum_a)
计算结果为5050，结果正确，但是需要我们思考的是，有没有更简洁的算法呢？
聪明的高斯想出了一个巧妙的解法，将原求和数列复制一份后反转，与原数列相加，再求和，
最终得到的结果即为原数列和的两倍，除以2即可得到答案，代码实现如下：
sum_a = (1 + 100) * 100 / 2
print(sum_a)
1. 枚举算法
1)，枚举算法的定义：
在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么该结论是可靠 的，这种归纳方法叫做枚举法。
2)，枚举算法的思想是：
将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，舍弃不合适的。
3)，使用枚举算法解题的基本思路如下：
（1）确定枚举对象、范围和判定条件。
（2）逐一枚举可能的解并验证每个解是否是问题的解。
4)，枚举算法步骤：
（1）确定解题的可能范围，不能遗漏任何一个真正解，同时避免重复。
（2）判定是否是真正解的方法。
（3）为了提高解决问题的效率，使可能解的范围将至最小，
枚举算法实例
例一：百钱买白鸡
1，问题描述：
公鸡每只5元，母鸡每只3元，三只小鸡1元，用100元买100只鸡，问公鸡、母鸡、小鸡各多少只？
2，算法分析：
利用枚举法解决该问题，以三种鸡的个数为枚举对象,分别设为mj,gj和xj，用三种鸡的总数 （mj+gj+xj=100）和买鸡钱的总数（1/3*xj+mj*3+gj*5=100）作为判定条件，穷举各种鸡的个数。
#include<iostream>
using namespace std;
int main()
{
int mj=0, gj=0, xj=0; //定义变量分别表示母鸡、公鸡、小鸡并初始化
for (gj = 0; gj <= 20; gj++) //公鸡最多可买20个
{
for (mj = 0; mj <= 33; mj++) //母鸡最多可买33个
{
xj = 100 - gj - mj; // 三种鸡的总数是100只
if (xj % 3 == 0 && 5 * gj + 3 * mj + xj / 3 == 100) // 总花费为100元。
printf("公鸡为 %d 只，母鸡为 %d 只，小鸡为 %d 只！\n", gj, mj, xj);
}
}
system("pause");
return 0;
}
例二：使用枚举法解决“填写运算符问题”
1，问题描述：在下面的算式中，添加“+”、“-”，“*”，“/”,4个运算符，使得这个式子成立。
5 5 5 5 5=5
2，算法分析：
上述式子左侧有5个数字，一共需要4个运算符。根据题目要求，两个数字之间的运算符只能有4中选择。在 具体编程时，可以通过循环来填入各种运算符，然后再判断算式左侧的值是否等于右侧的值。并保证，当填入的 是除号时，则右侧的数不能为0，并且乘除的优先级高于加减的优先级。
#include<iostream>
int main()
{
int j, i[5]; // 循环变量，数组i用来表示4个运算符
int sign; // 累加运算时的符号；
int result; // 保存运算式子的结果值
int count=0; // 计数器，统计符合条件的方案
int num[6]; // 保存操作数
float left, right; //保存中间结果
char oper[5] = { ' ','+','-','*','/' }; //运算符
printf("输入5个数，之间用空格隔开：");
for (j = 1; j <= 5; j++)
scanf_s("%d",&num[j]);
printf("输入结果：");
scanf_s("%d",&result);
//注：这里i[1]代表的第一个运算符的意思，i[1]=1代表第一个运算符是“+”，i[1]=2代表第一个运算符是“减”，i[1]=3代表第一个运算符是“-”，i[1]=4代表第一个运算符是“/”
//注：这里i[2]代表的第二个运算符的意思，i[2]=1代表第二个运算符是“+”，i[2]=2代表第二个运算符是“减”，i[2]=3代表第二个运算符是“-”，i[2]=4代表第二个运算符是“/”
//i[3],i[4]依次类推。
for (i[1]=1; i[1]<=4; i[1]++) //循环4种运算符，1表示+，2表示-，3表示*，4表示/
{
if ((i[1]<4) || (num[2] != 0)) //运算符若是/,则第二个运算数不能为0，（注：“||”是或运算，两个条件至少要有一个成立，即第一个运算符为/时，第二个运算数不为0）
{
for (i[2]=1; i[2]<=4; i[2]++)
{
if ((i[2]<4)||(num[3]!= 0)) //当第二个运算符为/时，第三个运算数不为0
{
for (i[3] = 1; i[3] <= 4; i[3]++)
{
if ((i[3] < 4) ||( num[4] != 0)) //当第三个运算符为/时，第四个运算数不为0
{
for (i[4] = 1; i[4] <= 4; i[4]++)
{
if ((i[4] < 4) || (num[5] != 0)) //当第四个运算符为/时，第五个运算数不为0
{
left = 0;
right = num[1];
sign = 1;
//使用case语句，将4种运算符填到对应的空格位置，并进行计算
for (j = 1; j <= 4; j++)
{
switch (oper[i[j]])
{
case '+':
left = left + sign*right;
sign = 1;
right = num[j + 1];
break;
case '-':
left = left + sign*right;
sign = -1;
right = num[j + 1];
break;
case '*':
right = right*num[j + 1];
break;
case '/':
right = right / num[j + 1];
break;
}
}
//开始判断，如果运算式子的结果和输入的结果相同，则表示找到一种算法，并输出这个解
if (left + sign*right == result)
{
count++;
printf("%3d:",count);
for (j = 1; j <= 4; j++)
printf("%d%c",num[j],oper[i[j]]);
printf("%d=%d\n",num[5],result);
}
}
}
}
}
}
}
}
}
if (count == 0)
printf("没有符合要求的方法！\n");
system("pause");
return 0;
}
2. 二分查找算法（折半查找）
二分查找是一种算法，其输入是一个有序的元素列表（必须是有序的），如果查找的元素包含在列表中，二分查找返回其位置，否则返回NULL(或者返回-1)
比如说有一个1-100的数字，我随机的选择其中一个数字（假设为60），你需要以最少的次数猜到我所选择的数字，每次猜测后，我会告诉你大了，小了，对了。
假设你第一次从1开始猜，小了
第二次：2 小了
第三次：3 小了
……
第五十九次：59 小了
第六十次：60 对了
这是简单的查找，每次猜测只能排除一个数字，如果我想的数字是100，那么你可能需要从1猜到100了！
那么有没有更好的查找方式呢？
答案当然是有的。
如果我选的数字是60
第一次：你从50开始猜，那么我告诉你小了，就排除了接近一半的数字，因为你至少知道1-50都小了
第二次：你猜75，那么我告诉你大了，这样剩下的数字又少了一半！或许你已经想到了，我们每次猜测都是选择了中间的那个数字，从而使得每次都将余下的数字排除了一半。
第三次：接下来，很明显应该猜测63，大了
第四次：然后你猜56，小了
第五次：然后你猜59 小了
第六次：猜测61，大了
第七次，你就能很明确的告诉我，答案是60！
这样的查找方式，很明显比第一种要高效很多。第一种需要猜测60次才能猜出正确答案，而使用第二种方式，只需要七次就能猜出正确答案
或许看到这里你已经明白了，这就是二分查找的方法。为什么二分查找要求有序，从这里也可以看出来。一般而言，对于包含n个元素的列表，用二分查找最多需要logn步，而简单查找最多需要n步。
二分查找的思路：
对于一个顺序排列的数组而言，当查找区间有不止一个元素的时候（即左边界不超过右边界），每次循环取当前区间中间的元素与目标值比较，根据以下三种比较结果判断跳出循环或更新左右边界：
（1）目标值 = 中间元素
此时正好在在当前区间的中间找到目标值，跳出循环。
（2）目标值 > 中间元素
表示此时目标值在以中间元素为界的右区间，需要移动左边界以在右区间继续进行查找。
（3）目标值 < 中间元素
表示此时目标值在以中间元素为界的左区间，需要移动右边界以在左区间继续进行查找。
查找过程
1.假设数组中的数组按照升序排列，首先将数组中间位置的值和需要查找的数进行比较，
2.判断数组中间位置的值若大于所需要的值，则说明所需要查找的数在中间值的左边。如果小于所要查找的值，则说明该数在中间值的右边。
3.通过修改左右的范围，再一次进行找中间值，然后与所需的值进行判断直至找到我们要找的数。
%cuichunlei_20210423
clear
x=sort(randperm(40,20))
T=17
L=length(x)
l=1;
r=L;
mid=ceil((r-l+1)/2)
num=0
while l<=r
num=num+1;
fprintf('循环次数：%d\n',num)
if T==x(mid)
fprintf('the target of %d ,location is %d\n',T,mid)
break
elseif T>x(mid)
l=mid+1
mid=ceil((r-l+1)/2)+mid
elseif T<x(mid)
r=mid-1
mid=mid-ceil((r-l+1)/2)
end
end
if l>r
disp('cant find the number')
end
#include<stdio.h>
int main()
{
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int left = 0; \\左边的范围
int key = 5; \\需要查找的数
int right = sizeof(a) / sizeof(a[0]) - 1; \\右边的范围
while (left <= right)
{
int mid = left + (right - left) / 2; \\通过左右范围算出中间值
if (a[mid] > key)
{
right = mid - 1; \\调整右边范围
}
else if (a[mid] < key)
{
left = mid + 1; \\调整左边范围
}
else if (a[mid] == key)
{
printf("找到了!%d\n", mid);
break;
}
}
if (left > right)
{
printf("没找到\n");
}
return 0;
}
=======================================
int binary_search(int t) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (num[mid] == x) {
return 1;
} else if (x > num[mid]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return 0;
}
========================================
/**
* 二分查找普通实现。
* @param srcArray 有序数组
* @param key 查找元素
* @return 不存在返回-1
*/
public static int binSearch(int srcArray[], int key) {
int mid;
int start = 0;
int end = srcArray.length - 1;
while (start <= end) {
mid = (end - start) / 2 + start;
if (key < srcArray[mid]) {
end = mid - 1;
} else if (key > srcArray[mid]) {
start = mid + 1;
} else {
return mid;
}
}
return -1;
}
采用递归方式完成二分查找算法。代码如下所示。
/**
* 二分查找递归实现。
* @param srcArray 有序数组
* @param start 数组低地址下标
* @param end 数组高地址下标
* @param key 查找元素
* @return 查找元素不存在返回-1
*/
public static int binSearch(int srcArray[], int start, int end, int key) {
int mid = (end - start) / 2 + start;
if (srcArray[mid] == key) {
return mid;
}
if (start >= end) {
return -1;
} else if (key > srcArray[mid]) {
return binSearch(srcArray, mid + 1, end, key);
} else if (key < srcArray[mid]) {
return binSearch(srcArray, start, mid - 1, key);
}
return -1;
}
作业：用二分法求方程 x * sin(x) - x+8=0 在3--4之间的根。
1、Assumptions：（假设）
continuous on [l,u]（函数在区间内连续）
（函数有穿过x轴，即被x轴分割）
2、Algorithm（算法）
二分算法流程图：
模拟练习1：以函数f(x)=log_2 x的近似解为例【手算：f(x)=0时，x=1】
clear;
l = 0.000000001; %0不在log函数定义域内，取0+即可
u = 5; %取很大的整数值也可以
f1 = log2(l); %计算()
f2 = log2(u); %计算()
while (u-l) >= 0.000001 %进入循环（while的判断条件为：如果条件为真，则完成循环内操作）
r = (l + u)/2; %取中点r
f3 = log2(r); %计算中点的函数值
if f3*f2 < 0 %进入判断
l = r;
f1 = f3;
else
u = r;
f2 = f3;
end
end
disp(r) %显示找到的根
function f=factor(n) % function 输出形参表 = 函数名（输入形参表）；
if n<=1 % 停止递归函数调用条件
f=1;
else
f=n*factor(n-1)；
end
设输入n=5时，即在交互式命令窗口输入
factor(5)
ans =120
具体递归函数调用过程可以这么理解：
当输入n=5时；
f=5factor(4) ; factor（4）调用函数模块factor.m；即相当于n=4,则有：
f=factor(4)=4factor(3) ; 同理，factor（3）调用函数模块factor.m，则有：
f=factor(3)=3factor(2) ;
f=factor(2)= 2factor(1) ; factor(1)调用函数模块factor.m，因为 n<=1, 故得 f=1返回给f=factor(1),即f=factor（1）=1;接下来factor（1）的值返回给factor（2），一次类推，factor（2）返回给factor（3）…
将上面代码整理一下：
f=5factor(4) ; (1)
factor(4)=4factor(3) ; (2)
factor(3)=3factor(2) ; (3)
factor(2)= 2factor(1) ; (4)
factor(1)=1; (5)
....将过程(5)合并到（4），（4）合并到（3）.........最终合并到（1）得：f=5*4*3*2*1=120
函数递归调用为啥效率低？
递归在解决某些问题的时候使得我们思考的方式得以简化，代码也更加精炼，容易阅读。那么既然递归有这么多的优点，我们是不是什么问题都要用递归来解决呢？难道递归就没有缺点吗？今天我们就来讨论一下递归的不足之处。谈到递归就不得不面对它的效率问题。
为什么递归是低效的
还是拿斐波那契（Fibonacci）数列来做例子。在很多教科书或文章中涉及到递归或计算复杂性的地方都会将计算斐波那契数列的程序作为经典示例。如果现在让你以最快的速度用C#写出一个计算斐波那契数列第n个数的函数（不考虑参数小于1或结果溢出等异常情况），我不知你的程序是否会和下列代码类似：
1publicstaticulong Fib(ulong n)
2{
3return(n == 1 || n == 2) ? 1 : Fib(n - 1) + Fib(n - 2);
4}
这段代码应该算是短小精悍（执行代码只有一行），直观清晰，而且非常符合许多程序员的代码美学，许多人在面试时写出这样的代码可能心里还会暗爽。但是如果用这段代码试试计算Fib(1000)我想就再也爽不起来了，它的运行时间也许会让你抓狂。
看来好看的代码未必中用，如果程序在效率不能接受那美观神马的就都是浮云了。如果简单分析一下程序的执行流，就会发现问题在哪，以计算Fibonacci(5)为例：
从上图可以看出，在计算Fib(5)的过程中，Fib(1)计算了两次、Fib(2)计算了3次，Fib(3)计算了两次，本来只需要5次计算就可以完成的任务却计算了9次。这个问题随着规模的增加会愈发凸显，以至于Fib(1000)已经无法再可接受的时间内算出。
我们当时使用的是简单的用定义来求 fib(n)，也就是使用公式 fib(n) = fib(n-1) + fib(n-2)。这样的想法是很容易想到的，可是仔细分析一下我们发现，当调用fib(n-1)的时候，还要调用fib(n-2)，也就是说fib(n-2)调用了两次，同样的道理，调用f(n-2)时f(n-3)也调用了两次，而这些冗余的调用是完全没有必要的。可以计算这个算法的复杂度是指数级的。
说到递归，大家一定会联系到迭代，这里就一起分析下吧。。
1.所谓的递归慢到底是什么原因呢？
大家都知道递归的实现是通过调用函数本身，函数调用的时候，每次调用时要做地址保存，参数传递等，这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括：局部变量、形参、调用函数地址、返回值。那么，如果递归调用N次，就要分配N*局部变量、N*形参、N*调用函数地址、N*返回值。这势必是影响效率的。
2.用循环效率会比递归效率高吗？
递归与循环是两种不同的解决问题的典型思路。当然也并不是说循环效率就一定比递归高，递归和循环是两码事，递归带有栈操作，循环则不一定，两个概念不是一个层次，不同场景做不同的尝试。
2.1递归算法：
优点：代码简洁、清晰，并且容易验证正确性。（如果你真的理解了算法的话，否则你更晕）
缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极端难看的代码。
2.2循环算法：
优点：速度快，结构简单。
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。
2.3递归算法和循环算法总结：
1.一般递归调用可以处理的算法，也通过循环去解决常需要额外的低效处理。
2.现在的编译器在优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。
3.递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换，而不影响程序的阅读，那么替换成递归往往是好的。（例如：求阶乘的递归实现与循环实现。）
总结：可以用循环就尽量用循环。少用递归。
====================================
====================================
五大常用算法：分治、动态规划、贪心、回溯和分支界定
https://blog.csdn.net/vivian_ll/article/details/103253664
一、贪心法
贪心算法的含义：
贪心算法（也叫贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到全局最优解，得到的是局部最优解，关键是贪心策略的选择，不同的贪婪策略会导致得到差异非常大的结果。选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
一般步骤：
建立数学模型来描述问题；
把求解的问题分成若干个子问题；
对每一子问题求解，得到子问题的局部最优解；
把子问题的局部最优解合成原来问题的一个解。
经典问题：
贪心法是动态规划法的特例，如0-1背包，钱币找零问题，最小代价生成树（prim算法和cruskal算法），huffman算法，以及Dijkstra算法。
二、动态规划
基本思想：
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。
我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
应用场景：
适用动态规划的问题必须满足:最优化原理、无后效性和重叠性。
1.最优化原理（最优子结构性质）
最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。如果可以把局部子问题的解结合起来得到全局最优解，那这个问题就具备最优子结构。
2.无后效性
将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。即要求每个子问题的决策不能对后面其他未解决的问题产影响， 如果产生就无法保证决策的最优性。
3.子问题的重叠性
如果计算最优解时需要处理很多相同的问题，那么这个问题就具备重复子问题。
动态规划必须保证我们分割成的子问题也能按照相同的方法分割成更小的子问题， 并这些自问题的最终分割情况是可以解决的。
动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。
动态规划算法的核心就是提供了一个memory来缓存重复子问题的结果，避免了递归的过程中的大量的重复计算。动态规划算法的难点在于怎么将问题转化为能够利用动态规划算法来解决。当重复子问题的数目比较小时，动态规划的效果也会很差。如果问题存在大量的重复子问题的话，那么动态规划对于效率的提高是非常恐怖的。
一般步骤：
1 分析最优解的性质，并刻画其结构特征。
2 递归地定义最优值。
3 以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
根据计算最优值时得到的信息，构造一个最优解。
步骤(1)–(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4)可以省略，若需要求出问题的一个最优解，则必须执行步骤(4)。此时，在步骤(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中，根据所记录的信息，快速地构造出一个最优解。
在实际的做题中也可以这样去做：
1 确定子问题： 在这一步重点是分析那些变量是随着问题规模的变小而变小的， 那些变量与问题的规模无关。
2 确定状态：根据上面找到的子问题来给你分割的子问题限定状态。
3 推导出状态转移方程：这里要注意你的状态转移方程是不是满足所有的条件， 注意不要遗漏。
4 确定边界条件：先根据题目的限制条件来确定题目中给出的边界条件是否能直接推导出， 如果不行也可以尝试从边界条件反推（举个例子：a(n)→a(2)有递推关系， 但是a(2)→a(1)不符合上述递推关系， 我们就可以考虑用a(1)来倒推出a(2)， 然后将递推的终点设置为a(2)）;
5 确定实现方式：这个依照个人习惯，就像是01背包的两层for循环的顺序。
6 确定优化方法：很多时候你会发现走到这里步的时候你需要返回第1步重来。首先考虑降维问题（优化内存）， 优先队列、四边形不等式（优化时间）等等。
常用方法：
模型匹配法：熟练记忆并且理解LIS、LCS、01背包、完全背包、区间模型、树状模型。基本就是将原模型加以变化后加以套用
三要素法：
1）先确定阶段：如数塔问题， 先确定当前选的是第几层。
2）先确定状态：这是最常用的绝大多数的DP都是这么做的。
3）先确定决策：背包问题（选还是不选第i种物品）
寻找规律法：从小的状态开始推， 耐心找规律， 或者可以在本地暴力打表， 暴力出奇迹。
边界条件法： 一般边界时容易导出状态关系的地方。
增加约束条件法
经典问题：
如多段图问题，备忘录方法，求全路径最短路径的Floyd弗洛伊德算法，最长公共子序列，斐波那契数列问题。
三、分治法
分治法的含义：
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。 求出子问题的解，就可得到原问题的解。
运用分治策略解决的问题一般来说具有以下特点：
原问题可以分解为多个子问题。这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。
原问题在分解过程中，递归地求解子问题。由于递归都必须有一个终止条件，因此，当分解后的子问题规模足够小时，应能够直接求解。
在求解并得到各个子问题的解后应能够采用某种方式、方法合并或构造出原问题的解。
不难发现，在分治策略中，由于子问题与原问题在结构和解法上的相似性，用分治方法解决的问题，大都采用了递归的形式。在各种排序方法中，如归并排序、堆排序、快速排序等，都存在有分治的思想。
一般步骤：
分解，将要解决的问题划分成若干规模较小的同类问题；
求解，当子问题划分得足够小时，用较简单的方法解决；
合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
经典问题：
归并排序、堆排序、快速排序、二分查找、全排列问题、整数划分问题、求第k大元素。
四、回溯法
回溯法的含义：
回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
回溯法就是对隐式图的深度优先搜索算法。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含（剪枝过程），则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯法为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死(剪枝)那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。（回溯法 = 穷举 + 剪枝）
两个常用的剪枝函数：
约束函数：在扩展结点处减去不满足约束的子数
限界函数：减去得不到最优解的子树
用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2^h(n))或O(h(n)!)内存空间。
一般步骤：
针对所给问题，定义问题的解空间；
确定易于搜索的解空间结构；
以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
经典问题：
如n皇后，图的着色问题、求子集、字符串的排列等问题。
五、分支限界法
基本思想：
分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
分支限界法的搜索策略：
在当前节点（扩展节点）处，先生成其所有的儿子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处，计算一个函数值（限界），并根据函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。
一般步骤：
定义问题的解空间
确定解空间的结构
以广度优先方式搜索整个解空间
找出所要的解（限界函数的使用）
常见的两种分支限界法：
队列式(FIFO)分支限界法
队列式分支限界法将活节点表组织成一个队列，并将队列的先进先出原则选取下一个节点为当前扩展节点。
优先队列式分支限界法
优先队列式分支限界法将活节点表组织成一个优先队列，并将优先队列中规定的节点优先级选取优先级最高的下一个节点成为当前扩展节点。如果选择这种选择方式，往往将数据排成最大堆或者最小堆来实现。
经典问题：
01背包，最大团，单源最短路径，装载问题，布线问题。
可参考：分支限界法总结–例题(01背包，最大团，单源最短路径，装载问题，布线问题)
六、总结
动态规划和分治的区别和联系：
动态规划算法与分治法的相同点在于，都是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
动态规划与分治法的不同点在于，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的，而分治法的子问题相互独立且与原问题性质相同。
分支限界法与回溯法的区别：
（1）求解目标：回溯法的求解目标是遍历整个解空间，找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
贪婪、动态规划、回溯的区别和联系：
首先，这些方法所要解决的问题，一般都是决策问题。而贪心法一般是来求解最优问题的，而且他们其实都是在对问题的状态空间树进行搜索，在这个状态空间树中搜索最佳的路径以便求出最优策略。而贪心法是从上到下只进行深度搜索的，也就是说它是一口气走到黑的，一口气吃成胖子的，它的代价取决于子问题的数目，也就是树的高度，每次在当前问题的状态上作出的选择都是1，也就是说，它其实是不进行广度搜索的，这也造成了它的一个缺点：它得出的解不一定是最优解，很有可能是近似最优解。
而动态规划法在最优子结构的前提下，从状态空间树的叶子节点开始向上进行搜索，并且在每一步都根据叶子节点的当前问题的状况作出选择，从而作出最优决策，它的代价就是子问题的个数和可选择的数目，所以它求出的解一定是最优解。
回溯法是从上到下进行深度搜索，如果深度搜索没有进行到底而不满足决策函数了，那么再回去从最近的可以岔开的地方选择另一条路，继续之前的深度搜索，如果搜索到底，那么再通过for循环进行广度搜索。所以它也是深度搜索和广度搜索并行的。求出的解也一定是最优解。
最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。
最后，五大算法都有相通的地方，理解透彻还是要靠实战。五大算法是开发、算法类岗位应聘时手撕代码的常考题，尤其是动态规划和回溯，把LeetCode上经典题目都做一遍，基本就能理解个差不多了。
参考网址：
浅谈动态规划法与贪心法和回溯法的联系
五大常用算法之三：贪心算法
最常用的五大算法
五大经典算法
动态规划(1)：基本思路以及步骤
动态规划算法的基本步骤
分支限界法
分支限界法
五大常用算法——分支限界算法详解及经典例题
============================================
常用算法小技巧
说到算法技巧，必须再给大家再讲一波好用的算法技巧，不信，你继续往下看
1. 巧用数组下标
数组的下标是一个隐含的很有用的数组，特别是在统计一些数字，或者判断一些整型数是否出现过的时候。例如，给你一串字母，让你判断这些字母出现的次数时，我们就可以把这些字母作为下标，在遍历的时候，如果字母a遍历到，则arr[a]就可以加1了，即 arr[a]++;
通过这种巧用下标的方法，我们不需要逐个字母去判断。
我再举个例子：
问题：给你n个无序的int整型数组arr，并且这些整数的取值范围都在0-20之间，要你在 O(n) 的时间复杂度中把这 n 个数按照从小到大的顺序打印出来。
对于这道题，如果你是先把这 n 个数先排序，再打印，是不可能O(n)的时间打印出来的。但是数值范围在 0-20。我们就可以巧用数组下标了。把对应的数值作为数组下标，如果这个数出现过，则对应的数组加1。 代码如下：
public void f(int arr[]) {
int[] temp = new int[21];
for (int i = 0; i < arr.length; i++) {
temp[arr[i]]++;
}
//顺序打印
for (int i = 0; i < 21; i++) {
for (int j = 0; j < temp[i]; j++) {
System.out.println(i);
}
}
}利用数组下标的应用还有很多，大家以后在遇到某些题的时候可以考虑是否可以巧用数组下标来优化。
2. 巧用取余
有时候我们在遍历数组的时候，会进行越界判断，如果下标差不多要越界了，我们就把它置为0重新遍历。特别是在一些环形的数组中，例如用数组实现的队列。往往会写出这样的代码：
for (int i = 0; i < N; i++) {
if (pos < N) {
//没有越界
// 使用数组arr[pos]
else {
pos = 0;//置为0再使用数组
//使用arr[pos]
}
pos++;
}实际上我们可以通过取余的方法来简化代码
for (int i = 0; i < N; i++) {
//使用数组arr[pos] (我们假设刚开始的时候pos < N)
pos = (pos + 1) % N;
}3. 巧用双指针
对于双指针，在做关于单链表的题是特别有用，比如“判断单链表是否有环”、“如何一次遍历就找到链表中间位置节点”、“单链表中倒数第 k 个节点”等问题。对于这种问题，我们就可以使用双指针了，会方便很多。我顺便说下这三个问题怎么用双指针解决吧。
例如对于第一个问题
我们就可以设置一个慢指针和一个快指针来遍历这个链表。慢指针一次移动一个节点，而快指针一次移动两个节点，如果该链表没有环，则快指针会先遍历完这个表，如果有环，则快指针会在第二次遍历时和慢指针相遇。
对于第二个问题
一样是设置一个快指针和慢指针。慢的一次移动一个节点，而快的两个。在遍历链表的时候，当快指针遍历完成时，慢指针刚好达到中点。
对于第三个问题
设置两个指针，其中一个指针先移动k个节点。之后两个指针以相同速度移动。当那个先移动的指针遍历完成的时候，第二个指针正好处于倒数第k个节点。
你看，采用双指针方便多了吧。所以以后在处理与链表相关的一些问题的时候，可以考虑双指针哦。
4. 设置哨兵位
在链表的相关问题中，我们经常会设置一个头指针，而且这个头指针是不存任何有效数据的，只是为了操作方便，这个头指针我们就可以称之为哨兵位了。
例如我们要删除头第一个节点是时候，如果没有设置一个哨兵位，那么在操作上，它会与删除第二个节点的操作有所不同。但是我们设置了哨兵，那么删除第一个节点和删除第二个节点那么在操作上就一样了，不用做额外的判断。当然，插入节点的时候也一样。
有时候我们在操作数组的时候，也是可以设置一个哨兵的，把arr[0]作为哨兵。例如，要判断两个相邻的元素是否相等时，设置了哨兵就不怕越界等问题了，可以直接arr[i] == arr[i-1]?了。不用怕i = 0时出现越界。
当然我这只是举一个例子，具体的应用还有很多，例如插入排序，环形链表等。
5. 与递归有关的一些优化
（1）.对于可以递归的问题考虑状态保存
当我们使用递归来解决一个问题的时候，容易产生重复去算同一个子问题，这个时候我们要考虑状态保存以防止重复计算。例如我随便举一个之前举过的问题
问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？
这个问题用递归很好解决。假设 f(n) 表示n级台阶的总跳数法，则有
f(n) = f(n-1) + f(n - 2)。
递归的结束条件是当0 <= n <= 2时, f(n) = n。因此我们可以很容易写出递归的代码
public int f(int n) {
if (n <= 2) {
return n;
} else {
return f(n - 1) + f(n - 2);
}
}不过对于可以使用递归解决的问题，我们一定要考虑是否有很多重复计算。显然对于 f(n) = f(n-1) + f(n-2) 的递归，是有很多重复计算的。如
就有很多重复计算了。这个时候我们要考虑状态保存。例如用hashMap来进行保存，当然用一个数组也是可以的，这个时候就像我们上面说的巧用数组下标了。可以当arr[n] = 0时，表示n还没计算过，当arr[n] != 0时，表示f(n)已经计算过，这时就可以把计算过的值直接返回回去了。因此我们考虑用状态保存的做法代码如下：
//数组的大小根据具体情况来，由于int数组元素的的默认值是0
//因此我们不用初始化
int[] arr = new int[1000];
public int f(int n) {
if (n <= 2) {
return n;
} else {
if (arr[n] != 0) {
return arr[n];//已经计算过，直接返回
} else {
arr[n] = f(n-1) + f(n-2);
return arr[n];
}
}
}这样，可以极大着提高算法的效率。也有人把这种状态保存称之为备忘录法。
(2).考虑自底向上
对于递归的问题，我们一般都是从上往下递归的，直到递归到最底，再一层一层着把值返回。
不过，有时候当n比较大的时候，例如当 n = 10000时，那么必须要往下递归10000层直到 n <=2 才将结果慢慢返回，如果n太大的话，可能栈空间会不够用。
对于这种情况，其实我们是可以考虑自底向上的做法的。例如我知道
f(1) = 1;
f(2) = 2;
那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此，我们可以考虑使用自底向上的方法来做。
代码如下：
public int f(int n) {
if(n <= 2)
return n;
int f1 = 1;
int f2 = 2;
int sum = 0;
for (int i = 3; i <= n; i++) {
sum = f1 + f2;
f1 = f2;
f2 = sum;
}
return sum;
}我们也把这种自底向上的做法称之为递推。
总结一下
当你在使用递归解决问题的时候，要考虑以下两个问题
(1). 是否有状态重复计算的，可不可以使用备忘录法来优化。
(2). 是否可以采取递推的方法来自底向上做，减少一味递归的开销。
6、找出不大于N的最大的2的幂指数
传统的做法就是让 1 不断着乘以 2，代码如下：
int findN(int N){
int sum = 1;
while(true){
if(sum * 2 > N){
return sum;
}
sum = sum * 2;
}
}这样做的话，时间复杂度是 O(logn)，那如果改成位运算，该怎么做呢？如果要弄成位运算的方式，很多时候我们把某个数拆成二进制，然后看看有哪些发现。这里我举个例子吧。
例如 N = 19，那么转换成二进制就是 00010011（这里为了方便，我采用8位的二进制来表示）。那么我们要找的数就是，把二进制中最左边的 1 保留，后面的 1 全部变为 0。即我们的目标数是 00010000。那么如何获得这个数呢？相应解法如下：
1、找到最左边的 1，然后把它右边的所有 0 变成 1
2、把得到的数值加 1，可以得到 00100000即 00011111 + 1 = 00100000。
3、把 得到的 00100000 向右移动一位，即可得到 00010000，即 00100000 >> 1 = 00010000。
那么问题来了，第一步中把最左边 1 中后面的 0 转化为 1 该怎么弄呢？我先给出代码再解释吧。下面这段代码就可以把最左边 1 中后面的 0 全部转化为 1，
n |= n >> 1; n |= n >> 2; n |= n >> 4;
就是通过把 n 右移并且做或运算即可得到。我解释下吧，我们假设最左边的 1 处于二进制位中的第 k 位(从左往右数),那么把 n 右移一位之后，那么得到的结果中第 k+1 位也必定为 1,然后把 n 与右移后的结果做或运算，那么得到的结果中第 k 和 第 k + 1 位必定是 1;同样的道理，再次把 n 右移两位，那么得到的结果中第 k+2和第 k+3 位必定是 1,然后再次做或运算，那么就能得到第 k, k+1, k+2, k+3 都是 1，如此往复下去....
最终的代码如下
int findN(int n){
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;// 整型一般是 32 位，上面我是假设 8 位。
return (n + 1) >> 1;
}这种做法的时间复杂度近是 O(log(logn))，重点是，高逼格。
8 种常见的数据结构
多图，一文了解 8 种常见的数据结构-常见的5种数据结构 (51cto.com)
百度百科对数据结构的定义是：相互之间存在一种或多种特定关系的数据元素的集合。定义很抽象，需要大声地朗读几遍，才有点感觉。怎么让这种感觉来得更强烈，更亲切一些呢?我来列举一下常见的 8 种数据结构，数组、链表、栈、队列、树、堆、图、哈希表。
这 8 种数据结构有什么区别呢?
①、数组
优点：
按照索引查询元素的速度很快;
按照索引遍历数组也很方便。
缺点：
数组的大小在创建后就确定了，无法扩容;
数组只能存储一种类型的数据;
添加、删除元素的操作很耗时间，因为要移动其他元素。
②、链表
《算法(第 4 版)》一书中是这样定义链表的：
链表是一种递归的数据结构，它或者为空(null)，或者是指向一个结点(node)的引用，该节点还有一个元素和一个指向另一条链表的引用。
Java 的 LinkedList 类可以很形象地通过代码的形式来表示一个链表的结构：
public class LinkedList<E> {
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.这是一种双向链表，当前元素 item 既有 prev 又有 next，不过 first 的 prev 为 null，last 的 next 为 null。如果是单向链表的话，就只有 next，没有 prev。
单向链表的缺点是只能从头到尾依次遍历，而双向链表可进可退，既能找到下一个，也能找到上一个——每个节点上都需要多分配一个存储空间。
链表中的数据按照“链式”的结构存储，因此可以达到内存上非连续的效果，数组必须是一块连续的内存。
由于不必按照顺序的方式存储，链表在插入、删除的时候可以达到 O(1) 的时间复杂度(只需要重新指向引用即可，不需要像数组那样移动其他元素)。除此之外，链表还克服了数组必须预先知道数据大小的缺点，从而可以实现灵活的内存动态管理。
优点：
不需要初始化容量;
可以添加任意元素;
插入和删除的时候只需要更新引用。
缺点：
含有大量的引用，占用的内存空间大;
查找元素需要遍历整个链表，耗时。
③、栈
栈就好像水桶一样，底部是密封的，顶部是开口，水可以进可以出。用过水桶的小伙伴应该明白这样一个道理：先进去的水在桶的底部，后进去的水在桶的顶部;后进去的水先被倒出来，先进去的水后被倒出来。
同理，栈按照“后进先出”、“先进后出”的原则来存储数据，先插入的数据被压入栈底，后插入的数据在栈顶，读出数据的时候，从栈顶开始依次读出。
④、队列
队列就好像一段水管一样，两端都是开口的，水从一端进去，然后从另外一端出来。先进去的水先出来，后进去的水后出来。
和水管有些不同的是，队列会对两端进行定义，一端叫队头，另外一端就叫队尾。队头只允许删除操作(出队)，队尾只允许插入操作(入队)。
注意，栈是先进后出，队列是先进先出——两者虽然都是线性表，但原则是不同的，结构不一样嘛。
⑤、树
树是一种典型的非线性结构，它是由 n(n>0)个有限节点组成的一个具有层次关系的集合。
之所以叫“树”，是因为这种数据结构看起来就像是一个倒挂的树，只不过根在上，叶在下。树形数据结构有以下这些特点：
每个节点都只有有限个子节点或无子节点;
没有父节点的节点称为根节点;
每一个非根节点有且只有一个父节点;
除了根节点外，每个子节点可以分为多个不相交的子树。
下图展示了树的一些术语：
根节点是第 0 层，它的子节点是第 1 层，子节点的子节点为第 2 层，以此类推。
深度：对于任意节点 n，n 的深度为从根到 n 的唯一路径长，根的深度为 0。
高度：对于任意节点 n，n 的高度为从 n 到一片树叶的最长路径长，所有树叶的高度为 0。
树的种类有很多种，常见的有：
无序树：树中任意节点的子节点之间没有顺序关系。那怎么来理解无序树呢，到底长什么样子?
假如有三个节点，一个是父节点，两个是同级的子节点，那么就有三种情况：
假如有三个节点，一个是父节点，两个是不同级的子节点，那么就有六种情况：
三个节点组成的无序树，合起来就是九种情况。
二叉树：每个节点最多含有两个子树。二叉树按照不同的表现形式又可以分为多种。
完全二叉树：对于一颗二叉树，假设其深度为 d(d > 1)。除了第 d 层，其它各层的节点数目均已达最大值，且第 d 层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树。
拿上图来说，d 为 3，除了第 3 层，第 1 层、第 2 层 都达到了最大值(2 个子节点)，并且第 3 层的所有节点从左向右联系地紧密排列(H、I、J、K、L)，符合完全二叉树的要求。
满二叉树：一颗每一层的节点数都达到了最大值的二叉树。有两种表现形式，第一种，像下图这样(每一层都是满的)，满足每一层的节点数都达到了最大值 2。
第二种，像下图这样(每一层虽然不满)，但每一层的节点数仍然达到了最大值 2。
二叉查找树：英文名叫 Binary Search Tree，即 BST，需要满足以下条件：
任意节点的左子树不空，左子树上所有节点的值均小于它的根节点的值;
任意节点的右子树不空，右子树上所有节点的值均大于它的根节点的值;
任意节点的左、右子树也分别为二叉查找树。
基于二叉查找树的特点，它相比较于其他数据结构的优势就在于查找、插入的时间复杂度较低，为 O(logn)。假如我们要从上图中查找 5 个元素，先从根节点 7 开始找，5 必定在 7 的左侧，找到 4，那 5 必定在 4 的右侧，找到 6，那 5 必定在 6 的左侧，找到了。
理想情况下，通过 BST 查找节点，所需要检查的节点数可以减半。
平衡二叉树：当且仅当任何节点的两棵子树的高度差不大于 1 的二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。
平衡二叉树本质上也是一颗二叉查找树，不过为了限制左右子树的高度差，避免出现倾斜树等偏向于线性结构演化的情况，所以对二叉搜索树中每个节点的左右子树作了限制，左右子树的高度差称之为平衡因子，树中每个节点的平衡因子绝对值不大于 1。
平衡二叉树的难点在于，当删除或者增加节点的情况下，如何通过左旋或者右旋的方式来保持左右平衡。
Java 中最常见的平衡二叉树就是红黑树，节点是红色或者黑色，通过颜色的约束来维持着二叉树的平衡：
1)每个节点都只能是红色或者黑色
2)根节点是黑色
3)每个叶节点(NIL 节点，空节点)是黑色的。
4)如果一个节点是红色的，则它两个子节点都是黑色的。也就是说在一条路径上不能出现相邻的两个红色节点。
5)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
B 树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个的子树。数据库的索引技术里就用到了 B 树。
⑥、堆
堆可以被看做是一棵树的数组对象，具有以下特点：
堆中某个节点的值总是不大于或不小于其父节点的值;
堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
⑦、图
图是一种复杂的非线性结构，由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V，E)，其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。
上图共有 V0，V1，V2，V3 这 4 个顶点，4 个顶点之间共有 5 条边。
在线性结构中，数据元素之间满足唯一的线性关系，每个数据元素(除第一个和最后一个外)均有唯一的“前驱”和“后继”;
在树形结构中，数据元素之间有着明显的层次关系，并且每个数据元素只与上一层中的一个元素(父节点)及下一层的多个元素(子节点)相关;
而在图形结构中，节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。
⑧、哈希表
哈希表(Hash Table)，也叫散列表，是一种可以通过关键码值(key-value)直接访问的数据结构，它最大的特点就是可以快速实现查找、插入和删除。
数组的最大特点就是查找容易，插入和删除困难;而链表正好相反，查找困难，而插入和删除容易。哈希表很完美地结合了两者的优点， Java 的 HashMap 在此基础上还加入了树的优点。
哈希函数在哈希表中起着⾮常关键的作⽤，它可以把任意长度的输入变换成固定长度的输出，该输出就是哈希值。哈希函数使得一个数据序列的访问过程变得更加迅速有效，通过哈希函数，数据元素能够被很快的进行定位。
若关键字为 k，则其值存放在 hash(k) 的存储位置上。由此，不需要遍历就可以直接取得 k 对应的值。
对于任意两个不同的数据块，其哈希值相同的可能性极小，也就是说，对于一个给定的数据块，找到和它哈希值相同的数据块极为困难。再者，对于一个数据块，哪怕只改动它的一个比特位，其哈希值的改动也会非常的大——这正是 Hash 存在的价值!
尽管可能性极小，但仍然会发生，如果哈希冲突了，Java 的 HashMap 会在数组的同一个位置上增加链表，如果链表的长度大于 8，将会转化成红黑树进行处理——这就是所谓的拉链法(数组+链表)。
