Java算法入门以及常见时间复杂度的推导

发布网友 发布时间：2024-09-26 17:35

我来回答

共1个回答

热心网友 时间：2024-10-04 11:28

本文详细介绍了算法的入门知识，比如算法的定义，以及算法的时间复杂度推导和常见算法的时间复杂度。

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