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

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

时间、空间复杂度

  • 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)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/138282.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

应用程序处理:TCP模块的处理

1、应用程序处理 首先应用程序会进行编码处理&#xff0c;这些编码相当于 OSI 的表示层功能&#xff1b; 编码转化后&#xff0c;邮件不一定马上被发送出去&#xff0c;这种何时建立通信连接何时发送数据的管理功能&#xff0c;相当于 OSI 的会话层功能。 2、TCP 模块的处理 …

Acer宏碁暗影骑士5笔记本AN517-54原装出厂Win10系统工厂模式

宏基电脑原厂WINDOWS10系统自带所有硬件的驱动、NITROSENSE风扇键盘控制中心、Office办公软件、出厂主题壁纸LOGO、 Acer Care Center、Quick Access等预装程序 链接&#xff1a;https://pan.baidu.com/s/1Ovui_CvsUaF-TX0NbuhEVg?pwdcrmv 提取码&#xff1a;crmv 所需要工…

Hadoop-sqoop

sqoop 1. Sqoop简介及原理 简介&#xff1a; Sqoop是一款开源的工具,主要用于在Hadoop(Hive)与传统的数据库(mysq1.postgresql..)间进行数据的传递&#xff0c;可以将一个关系型数据库&#xff08;例如: MySQL ,Oracle ,Postgres等&#xff09;中的数据导进到Hadoop 的HDFS中&…

2、Window上的 虚拟机端口 暴露到 宿主机局域网教程

今天在公司的服务器主机上捣鼓虚拟机&#xff0c;要在虚拟机上安装一个oracle&#xff0c;虚拟机和主机能互相ping通的前提下&#xff0c;要将虚拟机上的端口号暴露在主机上&#xff0c;让项目组内的所有员工的电脑都能访问到该oracle数据库。 也就是电脑A 访问主机&#xff0…

计算机网络运维方向综合知识大全

一. 基础知识 1. 网络的组成 组成部分&#xff1a;硬件、软件、协议 硬件主要由主机&#xff08;也称端系统&#xff09;、通信链路&#xff08;如双绞线、光纤&#xff09;、交换设备&#xff08;如路由器、交换机等)和通信处理机&#xff08;如网卡)等组成。软件主要包括各种…

【SpringCloud】微服务技术栈入门1 - 远程服务调用、Eureka以及Ribbon

目录 远程服务调用RestTemplate Eureka简要概念配置 Eureka 环境设置 Eureka ClientEureka 服务发现 Ribbon工作流程配置与使用 Ribbon饥饿加载 远程服务调用 RestTemplate RestTemplate 可以模拟客户端来向另外一个后端执行请求 黑马给出的微服务项目中&#xff0c;有两个 …

【深度学习实验】前馈神经网络(六):自动求导

目录 一、实验介绍 二、实验环境 1. 配置虚拟环境 2. 库版本介绍 三、实验内容 0. 导入必要的工具包 1. 标量求导 2. 矩阵求导 3. 计算图 一、实验介绍 PyTorch提供了自动求导机制&#xff0c;它是PyTorch的核心功能之一&#xff0c;用于计算梯度并进行反向传播。自动求…

使用Java将PPT、PPTX和PDF转换为图片

从Office到图片—使用Java实现文件格式转换 PDF转图片1. 万事第一步2. 撸代码 PPT/PPTX转图片1. 万事第一步2. 撸代码验收一下 最近小雨遇到了一个需求&#xff0c;需要在前端小程序中嵌入展示Office文件的功能。然而&#xff0c;前端使用开源组件进行在线预览会导致性能消耗较…

windows下gvim的配置

一、vim配置文件 "查看自己的vimrc所在的目录 "在命令模式下 :echo $MYVIMRC"打开自己的vimrc文件 "在命令模式下 :e $MYVIMRC 二、排版 "查看自己当前的字体及大小 "在命令模式下 :set guifont?"设置默认的字体为仿宋_GB2312&#xff…

IDEA 2019 Springboot 3.1.3 运行异常

项目场景&#xff1a; 在IDEA 2019 中集成Springboot 3.1.3 框架&#xff0c;运行异常。 <?xml version"1.0" encoding"UTF-8"?><project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSch…

R语言贝叶斯广义线性混合(多层次/水平/嵌套)模型GLMM、逻辑回归分析教育留级影响因素数据...

全文下载链接&#xff1a;http://tecdat.cn/?p24203 本教程使用R介绍了具有非信息先验的贝叶斯 GLM&#xff08;广义线性模型&#xff09; &#xff08;点击文末“阅读原文”获取完整代码数据&#xff09;。 当前教程特别关注贝叶斯逻辑回归在二元结果和计数/比例结果场景中的…

Linux:冯诺依曼系统和操作系统的概念

文章目录 冯诺依曼体系结构冯诺依曼体系的理解 操作系统操作系统的基本定位操作系统的理解1 操作系统的理解2总结 本篇主要总结的是操作系统的基本认知和一些概念 冯诺依曼体系结构 那么上图表示的就是冯诺依曼体系结构&#xff0c;那这个体系结构是什么&#xff1f;为什么要先…

客户端和服务端信息交互模型

什么是客户端和服务端&#xff1f; 客户端&#xff1a;可以向服务器发请求&#xff0c;并接收返回的内容进行处理 服务器端&#xff1a;能够接收客户端请求&#xff0c;并且把相关资源信息返回给客户端的 当用户在地址栏中输入网址&#xff0c;到最后看到页面&#xff0c;中间都…

配置OSPFv3基本功能 华为笔记

1.1 实验介绍 1.1.1 关于本实验 OSPF协议是为IP协议提供路由功能的路由协议。OSPFv2&#xff08;OSPF版本2&#xff09;是支持IPv4的路由协议&#xff0c;为了让OSPF协议支持IPv6&#xff0c;技术人员开发了OSPFv3&#xff08;OSPF版本3&#xff09;。 无论是OSPFv2还是OSPFv…

服务器新建FTP文件备份的地址

步骤1&#xff1a;远程桌面连接 步骤2&#xff1a;输入服务器地址&#xff0c;账号&#xff0c;密码 服务器地址&#xff1a;IP地址 账号&#xff1a;Administrator 密码&#xff1a;123456 步骤3&#xff1a;点击这个一个小人的图标 步骤4&#xff1a;General–>Add–&g…

R语言进行孟德尔随机化+meta分析(1)---meta分析基础

目前不少文章用到了孟德尔随机化meta分析&#xff0c;今天咱们也来介绍一下&#xff0c;孟德尔随机化meta其实主要就是meta分析的过程&#xff0c;提取了孟德尔随机化文章的结果&#xff0c;实质上就是个meta分析&#xff0c;不过多个孟德尔随机化随机化的结果合并更加加强了结…

【数据链路层】网络基础 -- MAC帧协议与ARP协议

数据链路层认识以太网以太网帧格式(MAC帧)认识MAC地址对比理解MAC地址和IP地址认识MTUMTU对IP协议的影响MTU对UDP协议的影响MTU对于TCP协议的影响 再谈局域网转发原理&#xff08;基于协议&#xff09;ARP协议ARP协议的作用ARP协议的工作流程ARP数据报的格式 数据链路层 用于两…

《DevOps实践指南》- 读书笔记(九)

DevOps实践指南 25. 附录附录 1 DevOps 的大融合精益运动敏捷运动Velocity 大会运动敏捷基础设施运动持续交付运动丰田套路运动精益创业运动精益用户体验运动Rugged Computing 运动 附录 2 约束理论和核心的长期冲突附录 3 恶性循环列表附录 4 交接和队列的危害附录 5 工业安全…

【Java 基础篇】Java并发包详解

多线程编程是Java开发中一个重要的方面&#xff0c;它能够提高程序的性能和响应能力。然而&#xff0c;多线程编程也伴随着一系列的挑战&#xff0c;如线程安全、死锁、性能问题等。为了解决这些问题&#xff0c;Java提供了一套强大的并发包。本文将详细介绍Java并发包的各个组…

基于SpringBoot的在线商城系统设计与实现

目录 前言 一、技术栈 二、系统功能介绍 用户信息管理 商品分类管理 商品信息管理 轮播图管理 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff…