写点什么

比比看!Java 时间和空间的复杂度算法,3 分钟你能学会哪个?

发布于: 2021 年 05 月 05 日
比比看!Java时间和空间的复杂度算法,3分钟你能学会哪个?

今日分享开始啦,请大家多多指教~


前言

1.在平常我们所说的时间复杂度一般说的都是算法的最坏情况;2.时间复杂度度是一个函数,这个函数只能大致估一下这个算法的时间复杂度;3.空间复杂度是个算法在运行过程中额外占用存储空间大小的量度。

一、算法效率

算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间。

二、时间复杂度

1.时间复杂度的概念

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。

算法中的基本操作的执行次数,为算法的时间复杂度。从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。

  • 一个算法所花费的时间与其中语句的执行次数成正比例;

  • 算法中的基本操作的执行次数,为算法的时间复杂度。

2.大 O 的渐进表示法

实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大 O 的渐进表示法。

  • 大 O 符号(Big O notation):是用于描述函数渐进行为的数学符号

(1)推导大 O 阶方法

  1. 用常数 1 取代运行时间中的所有加法常数。

  2. 在修改后的运行次数函数中,只保留最高阶项。

  3. 如果最高阶项存在且不是 1,则去除与这个项目相乘的常数。得到的结果就是大 O 阶

代码如下(示例):

  • 所以 func 方法的执行次数为 1+N2+2*N+1+10

我看到 func 的执行次数,如果当我们的 N 非常大时,假设 N = 100,那么这里的+1 和+10 是不是可以忽略了,因为 1002=10000,在一万面前+1 和+10 可以说是微乎其微了,所以+1 和+10 没什么区别。

这就用到了前面说了推导大 O 阶方法。

  • 用常数 1 取代运行时间中的所有加法常数。

就变成了 1+N2+2*N+1+1;

再来看

  • 在修改后的运行次数函数中,只保留最高阶项。

简化后 N2

  • 如果最高阶项存在且不是 1,则去除与这个项目相乘的常数。得到的结果就是大 O 阶。

这里我们的最高阶项是 2,但前面没有常数所以没必要去除,如果 N2 前面还有个 2 就是 2N2 就要去除 2 变成 N2;

所以使用大 O 的渐进表示法以后,Func 的时间复杂度为 O(N2)。

通过上面我们会发现大 O 的渐进表示法去掉了那些对结果影响不大的项,简洁明了地表示出了执行次数。时间复杂度是一个函数,只能大致估一下这个算法的时间复杂度。

3.时间复杂度的三种情况

另外有些算法的时间复杂度存在最好、平均和最坏情况。

(1) 最坏情况

  • 最坏情况:任意输入规模的最大运行次数(上界) 也就是 O(N);

这里的 N 代表的是问题的规模;

(2)最好情况

  • 任意输入规模的最小运行次数(下界) 也就是 O(1);

(3)平均情况

  • 任意输入规模的期望运行次数;

注意:这里的平均情况并不是最好和最坏情况相加的平均值,而是我们期望运行的次数,有时候平均情况可能和最好或者是最坏情况一样。

  • 在平常我们所说的时间复杂度一般说的都是算法的最坏情况。

4.常见时间复杂度计算举例

1.例子

示例 1:

1+2*N+1+10 通过推导大 O 阶方法后:时间复杂度为 O(N);

示例 2:

时间复杂度为:O(M+N);

示例 3:

这里的时间复杂度为 O(1),因为传进来的 N 并没有使用;

2.冒泡排序时间复杂度

示例 4:这是一个冒泡排序,我们来求一下它的最好最坏和平均情况的时间复杂度。

  • 最好:O(N)

  • 最坏:O(N2)

  • 平均:O(N)

这是一个经过优化后的冒泡排序,最好的情况就是该组数据已经是有序的了,所以只需走一遍就好了,也是是 O(N)。

而最坏的情况就把数组全部遍历了一遍就是 N2;

我们前面说过平均情况就是我们个期望的情况,我们期望的当然就是 O(N)。

3.二分查找的时间复杂度

我们知道求时间复杂度一般求的都是最坏的情况,二分查找只有当我们找最旁边那两个个数时才是最坏情况,我们就假设我们要找的就是最边边的那个数。



所以二分查找的时间复杂度为 O(log2N)。

4.递归的时间复杂度

  • 递归的时间复杂度 = 递归的次数*每次递归执行的操作的次数;

示例 1:

这里的的递归次数为 N 次,这里没有循环,每次执行的是一个三目操作符相当于 1 次。所以为 N+1 次,时间复杂度就是 O(N)。

示例 2:这是一个递归实现的斐波那契数列;

斐波那契数列的递归次数其实就是一个等比数列求和,最后的执行次数为 (2n) - 1,通过通过推导大 O 阶方法最后的时间复杂度为 O(2N)。

时间复杂度只是一个大概的,当数字足够大时这里缺失的部分并不影响我们时间复杂度的计算。

三、空间复杂度

1.空间复杂度概念

空间复杂度是对一个算法在运行过程中临时(额外)占用存储空间大小的量度;

占用存储空间大小的量度 。

空间复杂度不是程序占用了多少 bytes 的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。

空间复杂度计算规则基本跟实践复杂度类似,也使用大 O 渐进表示法。

2.空间复杂度的计算

(1) 冒泡排序

  • 这个冒泡排序的空间复杂度为 O(1);

为什么呢?因为空间复杂度是为了解决一个问题额外申请了其他变量,这里的 array 数组并不是额外的它是必须的,但这里的 sorted 是额外申请的,它每循环一次就定一次为什么不是 O(N)呢?因为每循环一次这个变量是不是不要了呢?所以来来回回就是这一个变量。

(2) 斐波那契数列

这里的空间复杂度为 O(N);这里为了求第 1~N 的斐波那契数列的代码,为了解决这个问题申请了一个额外的数组的空间,空间大小为 N+1。因为 1 是常数项,所以这个代码的空间复杂度为 O(N)。

(3)递归

这是一个求阶层的递归,他的空间复杂度为 O(N);因为递归在递的过程中,每递一次都会都会创建一个临时变量。

小结

在计算机发展的早期,计算机的存储容量很小,所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。因为现在的内存不像以前那么贵,所以经常听到过牺牲空间来换取时间的说法。


今日份分享已结束,请大家多多包涵和指点!

用户头像

还未添加个人签名 2021.04.20 加入

Java工具与相关资料获取等WX: pfx950924(备注来源)

评论

发布
暂无评论
比比看!Java时间和空间的复杂度算法,3分钟你能学会哪个?