Java实现几种最短路径问题

前言

最短路径问题在现实处处可见,而且针对不同的情形都需要具体分析才会找到最好解法。

最短路径Floyd算法

一支部队急行军,要经过A,B,C,D据点,这四个据点之间有些之间有路到达,有些没有。为了最大的节约时间,部队指挥部需要知道任意两个据点之间的最短时间。以下是两两之间所花的时间(如下图所示):

那么如何才能让两个据点之间花的时间变短?加入第三个据点即可。因此判断条件就出来了:
两个据点之间花费的时间如果比加入第三个据点的时间长,那么两个据点之间的最短时间即是加入第三个据点的时间之和。
这样Floyd算法的Java实现如下(核心代码就是上面的判断,边的权值全部提前赋值):

Floyd算法容易理解,并且可以算出任意两个点之间的最短距离。不难得出,Floyd算法的时间复杂度为O(n3),空间复杂度为O(n2),n为顶点的个数。

单源最短路径Dijkstra

还有一种常见的问题,也就是单源最短路径。求出1号顶点到其它顶点的最短距离:

类似Floyd算法,我们在核心代码里面直接就给出图的邻接矩阵,避免不必要的代码。

该算法同样和顶点关系密切,其时间复杂度为O(n2),空间复杂度也只需要存储图的邻接矩阵或者邻接链表即可。

0

二叉树的最大距离

写一个程序,让系统任务管理器的CPU使用曲线为50%,进阶是如何让 曲线为正弦曲线[1]。还有,如何实现双线程高效下载[2]。都是比较有意思、实用的例子。


##最大距离##

现在有一个题:求二叉树中节点的最大距离。这种题目一看感觉就是必须用到递归。_算法导论_上说递归算法可能将问题划分为规模不同的子问题。而寻找最小子问题就是关键。

解法如下:


这里的最小子问题是root==NULL或者可以看做root->LNode==NULLroot->RNode==NULL。所有的节点都是递归到了这一步得到MaxLen的初始化值。

MaxLen用来实时更新最大距离。

0

如何理解算法的时间复杂度和空间复杂度?

算法(Algorithm)是用来操作数据,解决问题的一组代码。就好比汽车的发动机调校,同样的发动机,让不同水平的工程师来调校,可能性能会差很多。

那我们优化算法也是一样,就两个衡量指标,时间维度和空间维度。

  • 时间维度:是指执行当前算法所消耗的时间,通常用「时间复杂度」来描述。
  • 空间维度:是指执行当前算法需要占用多少内存空间,通常用「空间复杂度」来描述。

就像汽车的驾驶乐趣和油耗,其实是不可兼得的,只能说尽量去找到一个平衡点。

一、时间复杂度

如何知道一个算法的时间复杂度?可以直接把它运行一遍,这样当然可以,但是这种方法受运行环境机器的影响较大。另外,我们应该是先胸有成竹,再泼墨挥毫。

如何才能做到胸有成竹呢?大O表示法,即 T(n) = O(f(n))。

在大O符号表示法中,时间复杂度的公式是: T(n) = O( f(n) ),其中f(n) 表示每行代码执行次数之和,而 O 表示正比例关系,这个公式的全称是:算法的渐进时间复杂度

看个例子,这段代码的时间复杂度是多少?

假设每行代码的执行时间都是一样的,我们用 1颗粒时间 来表示,那么这个例子的第一行耗时是1个颗粒时间,第三行的执行时间是 n个颗粒时间,第四行的执行时间也是 n个颗粒时间(第二行和第五行是符号,暂时忽略),那么总时间就是 1颗粒时间 + n颗粒时间 + n颗粒时间 ,即 (1+2n)个颗粒时间,即: T(n) = (1+2n)*颗粒时间,从这个结果可以看出,这个算法的耗时是随着n的变化而变化,因此,我们可以简化的将这个算法的时间复杂度表示为:T(n) = O(n)。

上面这段代码的时间复杂度为:O(n) ,为什么呢?

为什么可以这么去简化呢,因为大O符号表示法并不是用于来真实代表算法的执行时间的,它是用来表示代码执行时间的增长变化趋势的。

所以上面的例子中,如果n无限大的时候,T(n) = time(1+2n)中的常量1就没有意义了,倍数2也意义不大。因此直接简化为T(n) = O(n) 就可以了。

常见的时间复杂度量级有:

  • 常数阶O(1)
  • 对数阶O(logN)
  • 线性阶O(n)
  • 线性对数阶O(nlogN)
  • 平方阶O(n²)
  • 立方阶O(n³)
  • K次方阶O(n^k)
  • 指数阶(2^n)

上面从上至下依次的时间复杂度越来越大,执行的效率越来越低。

下面选取一些较为常用的来讲解一下(没有严格按照顺序):

常数阶O(1)

无论代码执行了多少行,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1),如:

上述代码在执行的时候,它消耗的时候并不随着某个变量的增长而增长,那么无论这类代码有多长,即使有几万几十万行,都可以用O(1)来表示它的时间复杂度。

线性阶O(n)

这个在最开始的代码示例中就讲解过了,如:

这段代码,for循环里面的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以用O(n)来表示它的时间复杂度。

对数阶O(logN)

还是先来看代码:

从上面代码可以看到,在while循环里面,每次都将 i 乘以 2,乘完之后,i 距离 n 就越来越近了。我们试着求解一下,假设循环x次之后,i 就大于 2 了,此时这个循环就退出了,也就是说 2 的 x 次方等于 n,那么 x = log2^n
也就是说当循环 log2^n 次以后,这个代码就结束了。因此这个代码的时间复杂度为:O(logn)

线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解,将时间复杂度为O(logn)的代码循环N遍的话,那么它的时间复杂度就是 n * O(logN),也就是了O(nlogN)。

就拿上面的代码加一点修改来举例:

平方阶O(n²)

平方阶O(n²) 就更容易理解了,如果把 O(n) 的代码再嵌套循环一遍,它的时间复杂度就是 O(n²) 了。
举例:

这段代码其实就是嵌套了2层n循环,它的时间复杂度就是 O(n*n),即 O(n²)
如果将其中一层循环的n改成m,即:

那它的时间复杂度就变成了 O(m*n)

立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²) 去理解就好了,O(n³)相当于三层n循环,其它的类似。

除此之外,其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法,有点复杂,这里就不展开了。

二、空间复杂度

既然时间复杂度不是用来计算程序具体耗时的,那么空间复杂度也不是用来计算程序实际占用的空间的。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,我们用 S(n) 来定义。

空间复杂度比较常用的有:O(1)、O(n)、O(n²),我们下面来看看:

空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)
举例:

代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

空间复杂度 O(n)

我们先看一个代码:

这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)

以上,就是如何理解算法的时间复杂度和空间复杂度的解析。

0

java冒泡排序算法

代码示例

时间复杂度

如果我们的数据正序,只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值,即:Cmin=n-1;Mmin=0;所以,冒泡排序最好的时间复杂度为O(n)。

如果很不幸我们的数据是反序的,则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:

即最坏情况下时间复杂度为O(n2)【n的平方】。所以,冒泡排序总的平均时间复杂度为:O(n2) 。

0