当前位置: 首页 > news >正文

【数据结构】时间、空间复杂度

⭐ 作者:小胡_不糊涂
🌱 作者主页:小胡_不糊涂的个人主页
📀 收录专栏:浅谈数据结构
💖 持续更文,关注博主少走弯路,谢谢大家支持 💖

时间、空间复杂度

  • 1. 算法效率
  • 3. 时间复杂度
    • 3.1 时间复杂度的概念
    • 3.2 大O的渐进表示法
    • 3.3 推导大O阶方法
    • 3.4 常见时间复杂度计算举例
  • 4. 空间复杂度

在这里插入图片描述

1. 算法效率

算法效率分析分为两种:第一种是时间效率,第二种是空间效率

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

在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

3. 时间复杂度

3.1 时间复杂度的概念

时间复杂度的定义: 在计算机科学中,算法的时间复杂度是一个数学函数,它定量描述了该算法的运行时间
一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。

但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

3.2 大O的渐进表示法

试计算下面代码中的 func1 基本操作执行了多少次?

void func1(int N){int count = 0;for (int i = 0; i < N ; i++) {for (int j = 0; j < N ; j++) {count++;}}for (int k = 0; k < 2 * N ; k++) {count++;}int M = 10;while ((M--) > 0) {count++;}System.out.println(count);
}

Func1 执行的基本操作数为:N* N+2* N+10

在这里插入图片描述

  • N = 10 F(N) = 130
  • N = 100 F(N) = 10210
  • N = 1000 F(N) = 1002010

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

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

3.3 推导大O阶方法

  • 用常数1取代运行时间中的所有加法常数。
  • 在修改后的运行次数函数中,只保留最高阶项。
  • 如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
    使用大O的渐进表示法以后,Func1的时间复杂度为:
    N = 10 F(N) = 100
    N = 100 F(N) = 10000
    N = 1000 F(N) = 1000000

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

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

  • 最坏情况:任意输入规模的最大运行次数(上界)
  • 平均情况:任意输入规模的期望运行次数
  • 最好情况:任意输入规模的最小运行次数(下界)
    例如:在一个长度为N数组中搜索一个数据x
    最好情况:1次找到
    最坏情况:N次找到
    平均情况:N/2次找到

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

3.4 常见时间复杂度计算举例

实例1:

// 计算func2的时间复杂度?void func2(int N) {int count = 0;for (int k = 0; k < 2 * N ; k++) {count++;}int M = 10;while ((M--) > 0) {count++;}System.out.println(count);}

在这里插入图片描述

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

实例2:

// 计算func3的时间复杂度?void func3(int N, int M) {int count = 0;for (int k = 0; k < M; k++) {count++;}for (int k = 0; k < N ; k++) {count++;}System.out.println(count);}

在这里插入图片描述

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

实例3:

 // 计算func4的时间复杂度?void func4(int N) {int count = 0;for (int k = 0; k < 100; k++) {count++;}System.out.println(count);}

在这里插入图片描述

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

实例4:

// 计算bubbleSort的时间复杂度?void bubbleSort(int[] array) {for (int end = array.length; end > 0; end--) {boolean sorted = true;for (int i = 1; i < end; i++) {if (array[i - 1] > array[i]) {Swap(array, i - 1, i);sorted = false;}}if (sorted == true) {break;}}}

在这里插入图片描述

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

实例5:

// 计算binarySearch的时间复杂度?int binarySearch(int[] array, int value) {int begin = 0;int end = array.length - 1;while (begin <= end) {int mid = begin + ((end-begin) / 2);if (array[mid] < value)begin = mid + 1;else if (array[mid] > value)end = mid - 1;elsereturn mid;}return -1;}

在这里插入图片描述

上述代码基本操作执行最好1次,最坏log2(N)次,时间复杂度为 O(log2(N))。
在算法分析中表示是底数为2,对数为N,有些地方会写成lgN。

实例6:

// 计算阶乘递归factorial的时间复杂度?long factorial(int N) {return N < 2 ? N : factorial(N-1) * N;}

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

实例7:

// 计算斐波那契递归fibonacci的时间复杂度?int fibonacci(int N) {return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);}

在这里插入图片描述

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

4. 空间复杂度

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

实例1:

// 计算bubbleSort的空间复杂度?void bubbleSort(int[] array){for (int end = array.length; end > 0; end--) {boolean sorted = true;//开辟一个空间for (int i = 1; i < end; i++) {if (array[i - 1] > array[i]) {Swap(array, i - 1, i);sorted = false;}}if (sorted == true) {break;}}}

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

实例2:

// 计算fibonacci的空间复杂度?int[] fibonacci(int n) {long[] fibArray = new long[n + 1];//开辟了n个空间fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n ; i++) {fibArray[i] = fibArray[i - 1] + fibArray [i - 2];}return fibArray;}

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

实例3:

// 计算阶乘递归Factorial的空间复杂度?long factorial(int N) {return N < 2 ? N : factorial(N-1)*N;}

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

相关文章:

【数据结构】时间、空间复杂度

⭐ 作者&#xff1a;小胡_不糊涂 &#x1f331; 作者主页&#xff1a;小胡_不糊涂的个人主页 &#x1f4c0; 收录专栏&#xff1a;浅谈数据结构 &#x1f496; 持续更文&#xff0c;关注博主少走弯路&#xff0c;谢谢大家支持 &#x1f496; 时间、空间复杂度 1. 算法效率3. 时…...

Databend 开源周报第 111 期

Databend 是一款现代云数仓。专为弹性和高效设计&#xff0c;为您的大规模分析需求保驾护航。自由且开源。即刻体验云服务&#xff1a;https://app.databend.cn 。 Whats On In Databend 探索 Databend 本周新进展&#xff0c;遇到更贴近你心意的 Databend 。 理解 SHARE END…...

iOS自动化测试方案(一):MacOS虚拟机保姆级安装Xcode教程

文章目录 一、环境准备二、基础软件三、扩展&#xff1a;usb拓展插件 一、环境准备 1、下载VMware虚拟机的壳子&#xff0c;安装并注册软件(可以百度注册码)&#xff0c;最新版本&#xff1a;v17 2、下MacOS系统iOS镜像文件&#xff0c;用于vmware虚拟机安装&#xff0c;当前镜…...

vue3 - Vue 项目处理GitHub Pages 部署后 _plugin-vue_export-helper.js 404

GitHub Demo 地址 在线预览 vue3项目打包后部署到github pages 后&#xff0c;预览网站提示下划线开头的一个文件_plugin-vue_export-helper访问不到&#xff0c;网络请求显示404 处理GitHub Pages 部署 _plugin-vue_export-helper.js 404 https://github.com/rollup/rollup/b…...

一百八十一、Hive——海豚调度HiveSQL任务时当Hive的计算引擎是mr或spark时脚本的区别(踩坑,附截图)

一、目的 当Hive的计算引擎是spark或mr时&#xff0c;发现海豚调度HQL任务的脚本并不同&#xff0c;mr更简洁 二、Hive的计算引擎是Spark时 &#xff08;一&#xff09;海豚调度脚本 #! /bin/bash source /etc/profile nowdatedate --date0 days ago "%Y%m%d" y…...

Linux 隔离网段下端口转发

设备在隔离网段下&#xff0c;设置端口转发。使A设备可访问C设备的服务 #!/bin/bash #输出成绩脚本 echo -n "请输入外网服务器的IP地址&#xff1a;" read score sudo iptables -t nat -A PREROUTING -p tcp --dport 1883 -j DNAT --to-destination $score:1883 s…...

【CDN和UDN】CDN和UDN技术特点以及使用场景

内容分发网络&#xff08;CDN&#xff09;和用户自定义网络&#xff08;UDN&#xff09;是两种不同的网络技术&#xff0c;在选择时&#xff0c;往往不能准备把握具不同的技术特点和应用场景。CDN 主要用于加速内容分发&#xff0c;而 UDN 则主要用于支持用户自定义的网络需求。…...

【Linux】改变缓存路径、清理缓存

写在前面 在做项目的过程中&#xff0c;服务器base路径下空间不足&#xff0c;准备在另一个目录下创建虚拟环境&#xff0c;但在安装的过程中&#xff0c;发现base路径下的空间还是在减少&#xff0c;后来经过学习了解到&#xff0c;pip安装下载依赖包时&#xff0c;会先下载缓…...

python+opencv寻找图片或视频中颜色进行追踪之HSV颜色处理

pythonopencv寻找图片或视频中颜色进行追踪之HSV颜色处理 1.颜色空间转换 import cv2img cv2.imread(1.jpg) # 转换为灰度图 img_gray cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)cv2.imshow(img, img) cv2.imshow(gray, img_gray) cv2.waitKey(0)cv2.cvtColor()用来进行颜色模…...

ubuntu 22.04 服务器网卡无IP地址

ssh连接服务器连接不上&#xff0c;提示如下&#xff1b; 连接显示器&#xff0c;ip addr ls 命令查看IP地址&#xff0c;有网卡但没有IP地址 solution&#xff1a; sudo dhclient enp10s0用于通过 DHCP 协议获取网络配置信息并为名为 enp10s0 的网络接口分配 IP 地址,enp1…...

基于SpringBoot的网上点餐系统

目录 前言 一、技术栈 二、系统功能介绍 用户功能模块 管理员功能模块 美食店功能模块 前台首页功能模块 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 系统管理也都将通过计算机进行整体智能化操作&#xff0c;对于网上点餐系统所牵扯的管理及数据保存…...

浅谈xss

XSS 简介 XSS,全称Cross Site Scripting,即跨站脚本攻击,是最普遍的Web应用安全漏洞。这类漏洞能够使得攻击者嵌入恶意脚本代码到正常用户会访问到的页面中,当正常用户访问该页面时,则可导致嵌入的恶意脚本代码的执行,从而达到恶意攻击用户的目的。需要强调的是,XSS不仅…...

悬崖边:企业如何应对网络安全漏洞趋势

在本文中&#xff0c;我们将讨论企业在处理漏洞时面临的挑战&#xff0c;解释安全漏洞是如何引发网络攻击的&#xff0c;以及为什么它会导致不可接受的事件。我们还将分享我们在识别趋势性漏洞方面的经验。 现代信息安全方法正在成为企业的工作流程。例如&#xff0c;不久前&a…...

MyBatis 动态 SQL、MyBatis 标签、MyBatis关联查询

MyBatis 动态 SQL、MyBatis 标签、MyBatis关联查询 1、MyBatis动态 sql 的特性2、MyBatis 标签2.1、if 标签&#xff1a;条件判断2.2、whereif 标签2.3、set 标签2.4、choose(when,otherwise) 语句2.5、trim2.6、MyBatis foreach 标签 3、整合案例3.1、XML3.2、测试类 4、sql 标…...

在Vue中使用Immutable.js

在Vue3中使用Immutable.js 以下是如何在Vue.js中使用Immutable.js的步骤&#xff1a; 首先&#xff0c;需要安装immutable.js。你可以通过npm或yarn来安装&#xff1a; npm install immutable或者 yarn add immutable在你的Vue组件中导入Immutable&#xff1a; import { Ma…...

基于Yolov8的工业端面小目标计数检测(1)

1.端面小目标计数数据集介绍 工业端面小目标计数类别:一类,类别名object 数据集大小:训练集864张,验证集98张 缺陷特点:小目标计数,检测难度大,如下图所示; 1.1 小目标定义 1)以物体检测领域的通用数据集COCO物体定义为例,小目标是指小于3232个像素点(中物体是指…...

1.什么是jwt?jwt的作用是什么?2.jwt的三个部分是什么?三者之间的关系如何?3.JWT运行的流程是什么

1. **什么是JWT&#xff1f;JWT的作用是什么&#xff1f;** JWT&#xff08;JSON Web Token&#xff09;是一种用于在不同系统或组件之间传输信息的紧凑且安全的标准。它的作用主要有两个方面&#xff1a; - **身份验证&#xff08;Authentication&#xff09;**&#xf…...

十三、MySql的视图

文章目录 一、前言二、定义三、为什么使用视图四、基本使用&#xff08;—&#xff09;创建视图&#xff08;二&#xff09;案例1.修改了视图&#xff0c;对基表数据有影响2.修改了基表&#xff0c;对视图有影响3.删除视图 五、视图规则和限制 一、前言 通过视图&#xff0c;可…...

MFC扩展库BCGControlBar Pro v33.6亮点 - 流程图、Ribbon Bar功能升级

BCGControlBar库拥有500多个经过全面设计、测试和充分记录的MFC扩展类。 我们的组件可以轻松地集成到您的应用程序中&#xff0c;并为您节省数百个开发和调试时间。 BCGControlBar专业版 v33.6已正式发布了&#xff0c;此版本包含了对图表组件的改进、带隐藏标签的单类功能区栏…...

前端 JS 经典:文件流下载

重点&#xff1a;调用接口时&#xff0c;一定要配置 responseType 的值为 blob&#xff0c;不然获取的文件流&#xff0c;不会转义成 blob 类型的文件。 1. 接口返回文件流 // BLOB (binary large object)----二进制大对象&#xff0c;是一个可以存储二进制文件的容器 // 下载…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...