龙空技术网

如何判断一个算法的好坏?(2)

JAVA一问一答 83

前言:

现在咱们对“评价算法的优劣的标准”大概比较关心,朋友们都想要分析一些“评价算法的优劣的标准”的相关知识。那么小编也在网络上汇集了一些有关“评价算法的优劣的标准””的相关文章,希望小伙伴们能喜欢,大家一起来学习一下吧!

上期我们聊到了判断一个算法的好坏,就是要看这个算法快不快,使用的空间省不省。我们通过时间复杂度来分析这个算法快不快,通过空间复杂度来分析这个算法使用的空间省不省。

上期我们通过 5 个例子来介绍了时间复杂度的分析方法,五个例子的时间复杂度分别是:

例1:T(n)=O(3)

例2:T(n)=O(1+2*1000)

例3:T(n)=O(1+2*n)

例4:T(n)=O(2n2+n +1)

例5:T(n)=O(1+2* log3n)

下面我们介绍下几个时间复杂度分析的小技巧:

1、如果代码的执行次数是一个已知的数,即使这段代码执行了100万次,只要这个100万是常量,那么这段代码的执行时间也是一个常量,即使执行 100 万次代码需要很久的时间,但是从时间复杂度代表的含义来看(一个算法执行效率与数据规模增长的变化趋势),当数据规模 n 为无限大时,100 万次的常量也可以被忽略掉。因为它本身对增长趋势并没有影响。

因此上述例子中,例1、例2就可以变为T(n) =O(1),例 3 则可以变成T(n) =O(n),例5则可以变成 T(n) = O(logn)。

2、总复杂度等于量级最大的那段代码的复杂度。即上述的例 4,我们可以写成T(n) =O(n2)。因为当数据规模 n 为无限大时,n2的影响比 n 的大得多,n 的影响可以忽略。也就是说,分析一段代码的时间复杂度时,我们只需关注量级最大的那段代码即可。

3、当出现嵌套时,比如一个循环内有另外一个循环,嵌套代码的复杂度就等于嵌套内外代码复杂度的乘积。例如如下代码:

public static void count(int n){       int sum = 0;       for (int i = 1;i <= n;i++){           for(int j = 1;j <= n;j=j*3){                 sum = sum + i*j;			 			}			 }}

上述代码的时间复杂度就可以用外层的 O(n) 与内层的 O(logn)相乘,变成O(nlogn)。

对于时间复杂度的量级,我们可以大致分为两类:

多项式量级:O(1)、O(logn)、O(n)、O(nlogn)、O(nk)

非多项式量级:O(2n)和O(n!)

其中当数据规模 n 越来越大时,非多项式量级算法的执行时间会急剧增加,代码的执行时间会无限增长。所以,非多项式时间复杂度的算法其实是非常低效的算法。

下方,我画出了部分多项式量级的增长趋势示意图,大家可以参考下:

时间复杂度还有更为复杂的 最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度、均摊时间复杂度等,这里因为篇幅有限,我们就不做讨论了,感兴趣的同学可以自行学习。

空间复杂度

理解了前面的时间复杂度的分析方法,再来看空间复杂度就简单很多了。之前我们说过,空间复杂是用来分析算法省不省的,而时间复杂度又叫做渐进时间复杂度表示法,空间复杂度则被称为渐进空间复杂度表示法,表示算法的存储空间与数据规模之间的增长关系。

我们同样通过一些例子来看一下,代码的空间复杂度怎么分析:

例1:

int[] nums = new int[500000];for(int i = 0;i < 500000;i++){ 		nums[i] = i;}

这段代码先新建一个长度为50万的数组,然后给这个数组循环赋值。这段代码所使用的空间即为这个长度为50万的数组所使用的空间。我们知道,即使这段代码循环了50万次,这段代码的时间复杂度仍然是O(1)。这段代码的空间复杂度其实也是如此,当数据规模 n为无限大时,50万次的常量也可以被忽略掉,因此这段代码的空间复杂度也是O(1)。

例2:

public static void count(int n){ 			int[] nums = new int[n];			for (int i = 1;i <= n;i++){ 				nums[i] = i; 			}}

例 2,我们将常量50万换成了变量 n,这段代码所使用的空间随着数据规模 n 的增长而增长。按照之前分析时间复杂度的方法进行分析,这段代码的空间复杂度为O(n)。

上面,我们通过2个简单的例子大概介绍了下空间复杂度的分析方法,空间复杂度的分析方法和时间复杂度的分析方法相差不大,在这我们就不过多描述了。我们常见的空间复杂度就是O(1)、O(n)、O(n2),像 O(logn)、O(nlogn)这样的对数阶复杂度平时都用不到。

至此,如何判断一个算法的好坏的内容我们就全部聊完了,复杂度分析的关键还是在于多加练习。

标签: #评价算法的优劣的标准