大家好，关于java算法大全很多朋友都还不太明白，今天小编就来为大家分享关于java十大经典算法的知识，希望对各位有所帮助！
在Java编程的世界里，算法就像是我们的武器库，有了它，我们才能在编程的道路上所向披靡。作为一名Java开发者，掌握一定的算法知识是必不可少的。今天，我就要为大家带来一篇全面的Java算法大全，从入门到精通，一网打尽所有核心算法。
一、什么是算法？
我们先来了解一下什么是算法。算法是一系列解决问题的步骤，它可以帮助我们高效地解决问题。在计算机科学中，算法是解决问题的核心，它决定了程序的性能和效率。
二、Java算法的分类
Java算法可以分为以下几类：
1. 基础算法：包括排序、查找、数据结构等。
2. 高级算法：包括动态规划、图算法、字符串处理等。
3. 算法优化：包括时间复杂度、空间复杂度等。
三、基础算法
1. 排序算法
排序算法是基础算法中最重要的一类，以下是一些常见的排序算法：
| 排序算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 冒泡排序 | O(n^2) | O(1) |
| 选择排序 | O(n^2) | O(1) |
| 插入排序 | O(n^2) | O(1) |
| 快速排序 | O(nlogn) | O(logn) |
| 归并排序 | O(nlogn) | O(n) |
| 堆排序 | O(nlogn) | O(1) |
2. 查找算法
查找算法主要包括线性查找和二分查找：
| 查找算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 线性查找 | O(n) | O(1) |
| 二分查找 | O(logn) | O(1) |
3. 数据结构
数据结构是算法的基础，以下是一些常见的数据结构：
| 数据结构 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 数组 | O(1) | O(n) |
| 链表 | O(1) | O(n) |
| 栈 | O(1) | O(n) |
| 队列 | O(1) | O(n) |
| 树 | O(logn) | O(n) |
四、高级算法
1. 动态规划
动态规划是一种解决最优化问题的算法，它将复杂问题分解为若干个简单子问题，并存储子问题的解，避免重复计算。
2. 图算法
图算法主要解决图相关的问题，如最短路径、最小生成树等。
3. 字符串处理
字符串处理算法主要解决字符串匹配、字符串搜索等问题。
五、算法优化
1. 时间复杂度
时间复杂度是衡量算法性能的重要指标，常见的复杂度有：
- O(1)：常数时间复杂度
- O(logn)：对数时间复杂度
- O(n)：线性时间复杂度
- O(nlogn)：线性对数时间复杂度
- O(n^2)：平方时间复杂度
- O(2^n)：指数时间复杂度
2. 空间复杂度
空间复杂度是衡量算法空间消耗的重要指标，常见的复杂度有：
- O(1)：常数空间复杂度
- O(n)：线性空间复杂度
- O(n^2)：平方空间复杂度
六、总结
本文为大家介绍了一些常见的Java算法，包括基础算法、高级算法和算法优化。掌握这些算法对于Java开发者来说至关重要。希望这篇文章能帮助你更好地掌握Java算法，提高编程能力。
我想说，学习算法是一个循序渐进的过程，需要不断地积累和总结。希望你能坚持学习，不断进步！
java十大算法
算法一：快速排序算法
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
算法步骤：
1从数列中挑出一个元素，称为”基准”（pivot），
2重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
算法二：堆排序算法
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的平均时间复杂度为Ο(nlogn)。
算法步骤：
创建一个堆H[0..n-1]
把堆首（最大值）和堆尾互换
3.把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4.重复步骤2，直到堆的尺寸为1
算法三：归并排序
归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
算法步骤：
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.重复步骤3直到某一指针达到序列尾
5.将另一序列剩下的所有元素
数据结构 java开发中常用的排序算法有哪些
排序算法有很多，所以在特定情景中使用哪一种算法很重要。为了选择合适的算法，可以按照建议的顺序考虑以下标准：
（1）执行时间
（2）存储空间
（3）编程工作
对于数据量较小的情形，（1）（2）差别不大，主要考虑（3）；而对于数据量大的，（1）为首要。
主要排序法有：
一、冒泡（Bubble）排序——相邻交换
二、选择排序——每次最小/大排在相应的位置
三、插入排序——将下一个插入已排好的序列中
四、壳（Shell）排序——缩小增量
五、归并排序
六、快速排序
七、堆排序
八、拓扑排序
一、冒泡（Bubble）排序
———————————-Code从小到大排序n个数————————————
void BubbleSortArray()
{
for(int i=1;i<n;i++)
{
for(int j=0;i<n-i;j++)
{
if(a[j]>a[j+1])//比较交换相邻元素
{
int temp;
temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;
}
}
}
}
————————————————-Code————————————————
效率 O（n²）,适用于排序小列表。
二、选择排序
———————————-Code从小到大排序n个数——————————–
void SelectSortArray()
{
int min_index;
for(int i=0;i<n-1;i++)
{
min_index=i;
for(int j=i+1;j<n;j++)//每次扫描选择最小项
if(arr[j]<arr[min_index])min_index=j;
if(min_index!=i)//找到最小项交换，即将这一项移到列表中的正确位置
{
int temp;
temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp;
}
}
}
————————————————-Code—————————————–
效率O（n²），适用于排序小的列表。
三、插入排序
——————————————–Code从小到大排序n个数————————————-
void InsertSortArray()
{
for(int i=1;i<n;i++)//循环从第二个数组元素开始，因为arr[0]作为最初已排序部分
{
int temp=arr[i];//temp标记为未排序第一个元素
int j=i-1;
while(j>=0&& arr[j]>temp)/*将temp与已排序元素从小到大比较，寻找temp应插入的位置*/
{
arr[j+1]=arr[j];
j–;
}
arr[j+1]=temp;
}
}
——————————Code————————————————————–
最佳效率O（n）；最糟效率O（n²）与冒泡、选择相同，适用于排序小列表
若列表基本有序，则插入排序比冒泡、选择更有效率。
四、壳（Shell）排序——缩小增量排序
————————————-Code从小到大排序n个数————————————-
void ShellSortArray()
{
for(int incr=3;incr<0;incr–)//增量递减，以增量3，2，1为例
{
for(int L=0;L<(n-1)/incr;L++)//重复分成的每个子列表
{
for(int i=L+incr;i<n;i+=incr)//对每个子列表应用插入排序
{
int temp=arr[i];
int j=i-incr;
while(j>=0&&arr[j]>temp)
{
arr[j+incr]=arr[j];
j-=incr;
}
arr[j+incr]=temp;
}
}
}
}
————————————–Code——————————————-
适用于排序小列表。
效率估计O（nlog2^n）~O（n^1.5），取决于增量值的最初大小。建议使用质数作为增量值，因为如果增量值是2的幂，则在下一个通道中会再次比较相同的元素。
壳（Shell）排序改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。
五、归并排序
———————————————-Code从小到大排序—————————————
void MergeSort(int low,int high)
{
if(low>=high) return;//每个子列表中剩下一个元素时停止
else int mid=(low+high)/2;/*将列表划分成相等的两个子列表,若有奇数个元素，则在左边子列表大于右侧子列表*/
MergeSort(low,mid);//子列表进一步划分
MergeSort(mid+1,high);
int [] B=new int [high-low+1];//新建一个数组，用于存放归并的元素
for(int i=low,j=mid+1,k=low;i<=mid&& j<=high;k++)/*两个子列表进行排序归并，直到两个子列表中的一个结束*/
{
if(arr[i]<=arr[j];)
{
B[k]=arr[i];
I++;
}
else
{ B[k]=arr[j]; j++;}
}
for(;j<=high;j++,k++)//如果第二个子列表中仍然有元素，则追加到新列表
B[k]=arr[j];
for(;i<=mid;i++,k++)//如果在第一个子列表中仍然有元素，则追加到新列表中
B[k]=arr[i];
for(int z=0;z<high-low+1;z++)//将排序的数组B的所有元素复制到原始数组arr中
arr[z]=B[z];
}
—————————————————–Code—————————————————
效率O（nlogn），归并的最佳、平均和最糟用例效率之间没有差异。
适用于排序大列表，基于分治法。
六、快速排序
————————————Code——————————————–
/*快速排序的算法思想：选定一个枢纽元素，对待排序序列进行分割，分割之后的序列一个部分小于枢纽元素，一个部分大于枢纽元素，再对这两个分割好的子序列进行上述的过程。*/void swap(int a,int b){int t;t=a;a=b;b=t;}
int Partition(int [] arr,int low,int high)
{
int pivot=arr[low];//采用子序列的第一个元素作为枢纽元素
while(low< high)
{
//从后往前栽后半部分中寻找第一个小于枢纽元素的元素
while(low< high&& arr[high]>= pivot)
{
–high;
}
//将这个比枢纽元素小的元素交换到前半部分
swap(arr[low], arr[high]);
//从前往后在前半部分中寻找第一个大于枢纽元素的元素
while(low<high&&arr [low ]<=pivot)
{
++low;
}
swap(arr [low ],arr [high ]);//将这个枢纽元素大的元素交换到后半部分
}
return low;//返回枢纽元素所在的位置
}
void QuickSort(int [] a,int low,int high)
{
if(low<high)
{
int n=Partition(a,low,high);
QuickSort(a,low,n);
QuickSort(a,n+1,high);
}
}
—————————————-Code————————————-
平均效率O（nlogn），适用于排序大列表。
此算法的总时间取决于枢纽值的位置；选择第一个元素作为枢纽，可能导致O（n²）的最糟用例效率。若数基本有序，效率反而最差。选项中间值作为枢纽，效率是O（nlogn）。
基于分治法。
七、堆排序
最大堆：后者任一非终端节点的关键字均大于或等于它的左、右孩子的关键字，此时位于堆顶的节点的关键字是整个序列中最大的。
思想：
(1)令i=l,并令temp＝ kl;
(2)计算i的左孩子j=2i+1;
(3)若j<＝n－1，则转(4),否则转(6);
(4)比较kj和kj+1,若kj+1>kj,则令j＝j＋1，否则j不变；
(5)比较temp和kj，若kj>temp，则令ki等于kj，并令i=j,j=2i+1,并转(3),否则转(6)
(6)令ki等于temp，结束。
—————————————–Code—————————
void HeapSort(SeqIAst R)
{//对R[1..n]进行堆排序，不妨用R[0]做暂存单元int I;BuildHeap(R)；//将R[1-n]建成初始堆for(i=n;i>1；i–)//对当前无序区R[1..i]进行堆排序，共做n-1趟。{R[0]=R[1]; R[1]=R[i]; R[i]=R[0];//将堆顶和堆中最后一个记录交换Heapify(R,1,i-1);//将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质}}—————————————Code————————————–
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1)，它是不稳定的排序方法。
堆排序与直接插入排序的区别:
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
八、拓扑排序
例：学生选修课排课先后顺序
拓扑排序：把有向图中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。
方法：
在有向图中选一个没有前驱的顶点且输出
从图中删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已输出（拓扑排序成功），或者当图中不存在无前驱的顶点（图中有回路）为止。
—————————————Code————————————–
void TopologicalSort()/*输出拓扑排序函数。若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR*/
{
int indegree[M];
int i,k,j;
char n;
int count=0;
Stack thestack;
FindInDegree(G,indegree);//对各顶点求入度indegree[0….num]
InitStack(thestack);//初始化栈
for(i=0;i<G.num;i++)
Console.WriteLine(“结点”+G.vertices[i].data+”的入度为”+indegree[i]);
for(i=0;i<G.num;i++)
{
if(indegree[i]==0)
Push(thestack.vertices[i]);
}
Console.Write(“拓扑排序输出顺序为：”);
while(thestack.Peek()!=null)
{
Pop(thestack.Peek());
j=locatevex(G,n);
if(j==-2)
{
Console.WriteLine(“发生错误，程序结束。”);
exit();
}
Console.Write(G.vertices[j].data);
count++;
for(p=G.vertices[j].firstarc;p!=NULL;p=p.nextarc)
{
k=p.adjvex;
if(!(–indegree[k]))
Push(G.vertices[k]);
}
}
if(count<G.num)
Cosole.WriteLine(“该图有环，出现错误，无法排序。”);
else
Console.WriteLine(“排序成功。”);
}
—————————————-Code————————————–
算法的时间复杂度O（n+e）。
Java算法入门以及常见时间复杂度的推导
本文详细介绍了算法的入门知识，比如算法的定义，以及算法的时间复杂度推导和常见算法的时间复杂度。
1算法定义通俗的说，算法是描述解决问题的方法。在计算机领域中，算法可以说是一组完成任务的指令，计算或者解决问题的步骤，因此，任何代码片段都可视为算法。
2算法的特性算法具有五个基本特性：输入、输出、有穷性、确定性和可行性。
2.1输入输出输入和输出特性比较容易理解，算法具有零个或多个输入。尽管对于绝大多数算法来说，输入参数都是必要的，但对于个别情况，如打印“helloworld！”这样的代码，不需要任何输入参数，因此算法的输入可以是零个。算法至少有一个或多个输出，算法是一定需要输出的，不需要输出，你用这个算法干吗？输出的形式可以是打印输出，也可以是返回一个或多个值等。
2.2有穷性有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。现实中经常会写出死循环的代码，这就是不满足有穷性。当然这里有穷的概念并不是纯数学意义的，而是在实际应用当中合理的、可以接受的“有边界”。你说你写一个算法，计算机需要算上个二十年，一定会结束，它在数学意义上是有穷了，可是媳妇都熬成婆了，算法的意义也不就大了。
2.3确定性确定性：算法的每一步骤都具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。算法的每个步骤被精确定义而无歧义。
2.4可行性可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。可行性意味着算法可以转换为程序上机运行，并得到正确的结果。尽管在目前计算机界也存在那种没有实现的极为复杂的算法，不是说理论上不能实现，而是因为过于复杂，我们当前的编程方法、工具和大脑限制了这个工作，不过这都是理论研究领域的问题，不属于我们现在要考虑的范围。
3算法时间复杂度3.1算法时间复杂度定义对于同一个问题的不同解决算法，应选择效率最高的算法，以最大限度地减少运行时间或占用空间，对于运行时间的计算就是计算算法的时间复杂度。
以n表示算法需要执行的操作数（规模），在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，又称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
这样用大写O()来体现算法时间复杂度的记法，我们称之为大O表示法。O这个符号的意思是“忽略重要项以外的内容”，读音同Order。
算法的速度指的并非时间，而是操作数的增速，一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。
3.2大O的推导如何推导一个算法的时间复杂度大O呢？这里有几条规则：
用常数1取代运行时间中的所有加法常数。
在修改后的运行次数函数中，只保留最高阶项。
如果最高阶项存在且不是1，则去除与这个项相乘的常数。
考虑n变大的情况。去除其他影响较小的部分，保留最大的部分。
实际上最重要的还是程序员的思维，如何得到运行次数的表达式,这需要一定的数学功底，比如求数列的通项公式！
3.3常见时间复杂度介绍下面是常见的大O运行时间复杂度：
O(1)，也叫常数时间，例如通过索引查找数组元素。
O(log n)，也叫对数时间，这样的算法包括二分查找。
O(n)，也叫线性时间，这样的算法包括简单查找。
O(n log n)，也叫线性对数时间，这样的算法包括快速排序。
O(n?)，也叫平方时间，这样的算法包括选择排序。
O(n?)，也叫立方时间，不常见。
O(2^n^)，也叫指数时间，不常见。
O(n!)，也叫阶乘时间，这样的算法包括旅行商问题的解决方案，包括写出1~n的所有全排列，不常见。
O(n^n^)，也叫完全平方时间，时间复杂度最高，不常见。
时间复杂度耗费时间从小到大排序如下：
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2^)<O(n^3^)<O(2^n^)<O(n!)<O(n^n^)
3.3.1 O(1)案例：求1+2+3+……+n的和？
针对上面的案例，我们可以写出时间复杂度为O(1)的非常快速的算法代码：
/***案例1:求1+2+3+4+……+n的和*使用高斯算法,无论n为多少,只需要下面一个步骤就能求出和,算法的时间复杂度为O(1)*/privatestaticlongO1(intn){longsum=(1+n)*n/2;returnsum;}代码中的完整时间复杂度为n(1+1)，根据大O推导规则“用常数1取代运行时间中的所有加法常数”，因为最终时间复杂度为O(1)。
3.3.2 O(n)线性时间的一般出现在循环结构中，并且相比常数时间O(1)会复杂很多，我们需要分析循环次数。
在上面的案例中，如果我们不采用高斯算法，而采用普通循环算法，那么算法的时间复杂度就是O(n)，即线性时间，意思是n为多少，就需要执行多少步！
下面的代码中，完整时间复杂度为O(1+n+1)，根据大O推导规则“考虑n变大的情况。去除其他影响较小的部分，保留最大的部分”，这里的O(1+n+1)中2始终不变，n越大时2的影响力就越小,因此去除常数2，最终时间复杂度为O(n)。
/***案例2:求1+2+3+4+……+n的和*使用传统循环相加算法,n为多少,需要循环多少次,排除*算法的时间复杂度为O(n),线性时间,算法效率明显要低于高斯算法*/privatestaticlongO2(intn){longsum=0;//n为多少,这里就需要循环多少次for(inti=1;i<=n;i++){sum+=i;}returnsum;}3.3.3 O(logn)当数据增大n倍时，耗时增大logn倍。
我们的二分查找,它的时间复杂度就是O(logn)，此时默认以2为底数。这里有个更简单案例：
/***案例3:对于2的x次方值n,求x的值是多少*采用下面的循环算法，循环逼近.*该算法可以换算为，有多少个2相乘后等于n，则会退出循环。由2^x=n得到x=log2n。*这个x就是时间复杂度，所以这个算法的时间复杂度为O(logn)。*/privatestaticlongO3(intn){longm=1;longx=0;while(m==n){//下面两句话看成一段时间复杂度为O(1)的循环程序步骤，需要执行logn次x++;m*=2;}returnx;}案例中总的时间复杂度为O(logn+3)，考虑n变大的情况。去除其他影响较小的部分，保留最大的部分，去除常数3，那么最终结果就是O(logn)
3.3.4 O(n?)当n足够大的时候，n的线性增长，复杂度将沿平方增长。
选择排序的算法时间复杂度就是O(n?)，求两个无序数组的交集时间复杂度也是O(n?)。下面来看更简单例子:
/***案例4:O(n^2)*输入为n时，需要执行n^2次内层的计算*/privatestaticlongO4(intn){longsum=0;longn2=n^2;for(inti=0;i<n2;i++){/*时间复杂度为O(1)的程序步骤*/sum+=i;}returnsum;}案例中总的时间复杂度为O(n?+3)，考虑n变大的情况。去除其他影响较小的部分，保留最大的部分，去除常数3，那么最终结果就是O(n?)。
3.4复杂语句的时间复杂度推导3.4.1多重循环对于多重循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c…，则这个循环的时间复杂度为 O(n×a×b×c…)。分析的时候应该由里向外分析这些循环。
privatestaticvoidO5(intn){for(inti=0;i<n;i++){for(intj=i;j<n;j++){/*时间复杂度为O(1)的程序步骤序列*/}}}我们来找一找n和时间复杂度的规律：由于当i=0时，内循环执行了n次，当i=1时，执行了n-1次，……当i=n-1时，执行了1次。所以总的执行次数为：
然后使用大O推导的方法：“只保留最高阶项”，那么去除n/2；“去除这个项相乘的常数“，也就是去除1/2，最终这段代码的时间复杂度为O(n^2^)。
3.4.2顺序语句对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度：
privatestaticlongO6(intn){//1次longsum=0;//n次for(inti=0;i<n;i++){/*时间复杂度为O(1)的程序步骤序列*/}//n(n+1)/2次for(inti=0;i<n;i++){for(intj=i;j<n;j++){/*时间复杂度为O(1)的程序步骤序列*/}}//1次returnsum;}此时时间复杂度为O(n^2^)。
3.4.3条件判断语句对于条件判断语句，总的时间复杂度等于其中时间复杂度最大的路径的时间复杂度。
privatestaticvoidO7(intn){if(n==1){//n次for(inti=0;i<n;i++){/*时间复杂度为O(1)的程序步骤序列*/}}else{//n(n+1)/2次for(inti=0;i<n;i++){for(intj=i;j<n;j++){/*时间复杂度为O(1)的程序步骤序列*/}}}}此时时间复杂度为 O(n^2^)。
3.4.4递归求第n项斐波那契数列的值，我们常用的方法是递归，因为看起来比较简单，如下：
privatestaticlongO8(intn){if(n<=1){return1;}else{returnO8(n-1)+O8(n-2);}}现在求它的时间复杂度。显然运行次数n小于等于2时，a(0)= a(1)= 1；n大于等于2时a(n)= a(n- 1)+ a(n- 2)+ 1，这里的 1是其中的加法算一次执行。我们可以把常数1省略，就变成了T(n)= T(n- 1)+ T(n- 2)，这明显是一个递推数列。
我们利用线性代数来求解，上面的线性递推数列的特征方程为：x^2=x+1，可以求得如下解：
那么
因为a1=1，a2=1，则有
解得
所以斐波那契数列的通项公式a(n)为:
也就是采用递归方式求第n项斐波那契数列的值的时间复杂度,可以看出来这是一个指数级的时间复杂度，相当的耗费时间，n稍微大一点基本上程序就会挂掉。
从上面我们也能看出来：
求复杂的时间复杂度需要大学数学的知识了；
代码中慎用递归。
4最坏情况与平均情况一个算法具体的时间复杂度可能不是固定的，比如，我们顺序查找一个有n个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为O(1)，但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度就是O(n)，这是最坏的一种情况了。
对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。平均运行时间很难通过分析得到，一般在没有特殊说明的情况下，都是指最坏时间复杂度。我们的O表示的时间复杂度就是最坏时间复杂度。
5算法空间复杂度算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。
若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)，而一般的递归算法就要有O(n)的空间复杂度了。
通常，我们都使用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。当不用限定词地使用“复杂度”时，由于空间复杂度难以计算，通常都是指时间复杂度。
作者：刘Java
java算法大全和java十大经典算法的问题分享结束啦，以上的文章解决了您的问题吗？欢迎您下次再来哦！
