搜索
首页Javajava教程Java时间复杂度与空间复杂度实例分析

一、算法效率

算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被 称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额 外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的 迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复 杂度。

二、时间复杂度

1.时间复杂度概念

一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复 杂度。也就是说当我们拿到一个代码,来看这个代码的时间复杂度的时候,主要是去找这个代码当中执行语句次数最多的代码执行了多少次。

2.大O的渐进表示法

看图分析:

Java时间复杂度与空间复杂度实例分析

当N的值越来越大,2N和10的值就可以忽略不记了。 

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

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

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

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

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

Java时间复杂度与空间复杂度实例分析

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。

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

最坏情况:任意输入规模的最大运行次数(上界)

平均情况:任意输入规模的期望运行次数

最好情况:任意输入规模的最小运行次数(下界) 

例如:在一个长度为N数组中搜索一个数据x

最好情况:1次找到

最坏情况:N次找到

平均情况:N/2次找到 

在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

计算时间复杂度  

例题1:

Java时间复杂度与空间复杂度实例分析

基本操作执行了2N+10次,通过推导大O阶方法知道,时间复杂度为 O(N)

例题2:

Java时间复杂度与空间复杂度实例分析

基本操作执行了M+N次,有两个未知数M和N,时间复杂度为 O(N+M)

例题3:

Java时间复杂度与空间复杂度实例分析

基本操作执行了100次,通过推导大O阶方法,时间复杂度为 O(1)

例题4:计算冒泡排序的时间复杂度

Java时间复杂度与空间复杂度实例分析

基本操作执行最好N次,最坏执行了(N*(N-1))/2次,通过推导大O阶方法+时间复杂度一般看最坏, 时间复杂度为 O(N^2

例题5:二分查找的时间复杂度

Java时间复杂度与空间复杂度实例分析

基本操作执行最好1次,最坏O(logN)次,时间复杂度为 O(logN) ps:logN在算法分析中表示是底数 为2,对数为N。有些地方会写成lgN。(建议通过折纸查找的方式讲解logN是怎么计算出来的)(因为二 分查找每次排除掉一半的不适合值,一次二分剩下:n/2 两次二分剩下:n/2/2 = n/4)

例题6:计算阶乘递归的时间复杂度

递归的时间复杂度 = 递归的次数*每次递归执行的次数

Java时间复杂度与空间复杂度实例分析

通过计算分析发现基本操作递归了N次,时间复杂度为O(N)。

例题7:计算斐波那契递归的时间复杂度

Java时间复杂度与空间复杂度实例分析

通过计算分析发现基本操作递归了2^N次,时间复杂度为O(2^N)。

规律: 

Java时间复杂度与空间复杂度实例分析

 2^0+2^1+2^2+2^3……2^(n-(n-1))

等比数列求和

Java时间复杂度与空间复杂度实例分析

 a1就代表第一项,q是等比就是2,1(1-2^n)/-1,相当于2^n+1,所以时间复杂度为O(2^n)

三、空间复杂度 

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes 的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度 类似,也使用大O渐进表示法。

 例题1:计算冒泡排序的空间复杂度

Java时间复杂度与空间复杂度实例分析

使用了常数个额外空间,所以空间复杂度为 O(1)

 例题2:计算斐波那契的空间复杂度

Java时间复杂度与空间复杂度实例分析

动态开辟了N个空间,空间复杂度为 O(N)

例题3:计算阶乘递归的空间复杂度

Java时间复杂度与空间复杂度实例分析

  递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)

以上是Java时间复杂度与空间复杂度实例分析的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:亿速云。如有侵权,请联系admin@php.cn删除
如何将Maven或Gradle用于高级Java项目管理,构建自动化和依赖性解决方案?如何将Maven或Gradle用于高级Java项目管理,构建自动化和依赖性解决方案?Mar 17, 2025 pm 05:46 PM

本文讨论了使用Maven和Gradle进行Java项目管理,构建自动化和依赖性解决方案,以比较其方法和优化策略。

如何使用适当的版本控制和依赖项管理创建和使用自定义Java库(JAR文件)?如何使用适当的版本控制和依赖项管理创建和使用自定义Java库(JAR文件)?Mar 17, 2025 pm 05:45 PM

本文使用Maven和Gradle之类的工具讨论了具有适当的版本控制和依赖关系管理的自定义Java库(JAR文件)的创建和使用。

如何使用咖啡因或Guava Cache等库在Java应用程序中实现多层缓存?如何使用咖啡因或Guava Cache等库在Java应用程序中实现多层缓存?Mar 17, 2025 pm 05:44 PM

本文讨论了使用咖啡因和Guava缓存在Java中实施多层缓存以提高应用程序性能。它涵盖设置,集成和绩效优势,以及配置和驱逐政策管理最佳PRA

如何将JPA(Java持久性API)用于具有高级功能(例如缓存和懒惰加载)的对象相关映射?如何将JPA(Java持久性API)用于具有高级功能(例如缓存和懒惰加载)的对象相关映射?Mar 17, 2025 pm 05:43 PM

本文讨论了使用JPA进行对象相关映射,并具有高级功能,例如缓存和懒惰加载。它涵盖了设置,实体映射和优化性能的最佳实践,同时突出潜在的陷阱。[159个字符]

Java的类负载机制如何起作用,包括不同的类载荷及其委托模型?Java的类负载机制如何起作用,包括不同的类载荷及其委托模型?Mar 17, 2025 pm 05:35 PM

Java的类上载涉及使用带有引导,扩展程序和应用程序类负载器的分层系统加载,链接和初始化类。父代授权模型确保首先加载核心类别,从而影响自定义类LOA

如何将Java的RMI(远程方法调用)用于分布式计算?如何将Java的RMI(远程方法调用)用于分布式计算?Mar 11, 2025 pm 05:53 PM

本文解释了用于构建分布式应用程序的Java的远程方法调用(RMI)。 它详细介绍了接口定义,实现,注册表设置和客户端调用,以解决网络问题和安全性等挑战。

如何使用Java的插座API进行网络通信?如何使用Java的插座API进行网络通信?Mar 11, 2025 pm 05:53 PM

本文详细介绍了用于网络通信的Java的套接字API,涵盖了客户服务器设置,数据处理和关键考虑因素,例如资源管理,错误处理和安全性。 它还探索了性能优化技术,我

如何在Java中创建自定义网络协议?如何在Java中创建自定义网络协议?Mar 11, 2025 pm 05:52 PM

本文详细介绍了创建自定义Java网络协议。 它涵盖协议定义(数据结构,框架,错误处理,版本控制),实现(使用插座),数据序列化和最佳实践(效率,安全性,维护

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解锁Myrise中的所有内容
3 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

WebStorm Mac版

WebStorm Mac版

好用的JavaScript开发工具

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

安全考试浏览器

安全考试浏览器

Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

螳螂BT

螳螂BT

Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。