数据结构的时间复杂度和空间复杂度

        

目录

        

时间复杂度

        空间复杂度


时间复杂度

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

        我们使用大O的渐进表示法来表示时间复杂度。

        怎么使用?

        先看例子:

        

        在这个例子中, 基本操作为变量 count 的 加加 操作,并且,执行次数与 参数 N 有关,操作次数为 N^2+2*N +10 

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

        所以现在我们应该怎么使用大O的渐进表示法表示呢?

        大O的渐进表示法:

        1.用 O(1) 表示固定的操作次数。

        2.在修改最后的运行次数的函数中,只保留最高次项,并且除去最高次项前面的系数,则为结果。

        

        显然,上面的示例代码就是第二种情况。表示成O(N^2)

        

        再来一个例子:

        

        这是一个二分查找的代码,代码结束可能有这几种情况:

        最好情况:运行一次找到。

        较好情况:运行一半次数找到。

        最坏情况:运行最后一次才找到。

        那么,在实际中我们⼀般情况关注的是最坏运行情况,这里的代码执行次数与元素个数有关,用 N 表示元素个数。则:

      

        由图分析得到:

        2^(循环次数 - 1)= N  -----> 循环次数 =  

        时间复杂度为也就是上图。 

         对数以2为底的情况下,可以简写成O(logN)

        

        空间复杂度

 空间复杂度是对代码在运行过程中临时占用存储空间大小的量度。

  空间复杂度也使用大O渐进表示法。

   例子1:

        

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

        

例子2:

        

        临时创建的空间大小与n有关,所以是动态开辟了n个空间,空间复杂度为O(n)

        

     例子3:

        

        这里每次递归都会调用函数add,调用就会开辟内存空间,调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SQL面试题——奔驰SQL面试题 车辆在不同驾驶模式下的时间

SQL面试题——奔驰SQL面试题 我们的表大致如下 CREATE TABLE signal_log( vin STRING COMMENTvehicle frame id, signal_name STRING COMMENTfunction name, signal_value STRING COMMENT signal value , ts BIGINT COMMENTevent timestamp, dt STRING COMMENTformat yyyy-mm…

Mac 使用mac 原生工具将mp4视频文件提取其中的 mp3 音频文件

简介 Hello! 非常感谢您阅读海轰的文章,倘若文中有错误的地方,欢迎您指出~ ଘ(੭ˊᵕˋ)੭ 昵称:海轰 标签:程序猿|C++选手|学生 简介:因C语言结识编程,随后转入计算机专业,获得过国家奖学金,有幸在竞赛中拿过一些国奖、省奖…已保研 学习经验:扎实基础 + 多做笔…

多模态与大模型技术赋能企业数据资产平台建设

文章目录 一、政策背景分析二、企业数据资产运营平台架构思路三、统一多模技术赋能企业数据底座建设四、大模型助力数据资产管理降本增效五、典型案例分享 一、政策背景分析 2023年10月,国家数据局正式挂牌,负责协调推进数据基础制度建设,并…

【CentOS】中的Firewalld:全面介绍与实战应用(上)

🐇明明跟你说过:个人主页 🏅个人专栏:《Linux :从菜鸟到飞鸟的逆袭》🏅 🔖行路有良友,便是天堂🔖 目录 一、引言 1、iptables 时代 2、firewalld 时代 3、 从 ipt…

使用 unicorn 和 capstone 库来模拟 ARM Thumb 指令的执行(一)

import binascii import unicorn import capstonedef printArm32Regs(mu):for i in range(66,78):print("R%d,value:%x"%(i-66,mu.reg_read(i)))def testhumb():CODE b\x1C\x00\x0A\x46\x1E\x00"""MOV R3, R0 的机器码:0x1C 0x00&#xf…

NVT新能德科技入职测评SHL题库更新:数字推理+演绎推理高分答案、真题解析

新能德的入职Verify测评主要考察应聘者的逻辑推理能力、数学能力、数据分析能力以及处理信息的能力。根据搜索结果,测评通常包含以下几个部分: 1. **语言理解**:这部分包括阅读理解、逻辑填空和语句排序。要求应聘者在17分钟内完成30题&#…

HBase理论_背景特点及数据单元及与Hive对比

本文结合了个人的笔记以及工作中实践经验以及参考HBase官网,我尽可能把自己的知识点呈现出来,如果有误,还请指正。 1. HBase背景 HBase作为面向列的数据库运行在HDFS之上,HDFS缺乏随机读写操作,HBase正是为此而出现。…

Linux:进程概念

文章目录 前言一、冯诺依曼体系二、操作系统(Operator System)2.1.操作系统的概念2.2 系统调⽤和库函数概念 三. 进程3.1 基本概念3.1.1 描述进程3.1.2 task_struct 3.2 查看进程3.2.1 getpid3.2.2 proc3.2.3 getppid 总结 前言 • 课本概念:程序的⼀个执⾏实例&am…

el-form el-table 前端排序+校验+行编辑

一、页面 <template><div class"bg" v-if"formData.mouldData?.length 0">当前暂无模板&#xff0c;点击<view class"add" click"addMould">立即创建</view></div><div v-else><el-col :x…

jmeter常用配置元件介绍总结之后置处理器

系列文章目录 安装jmeter jmeter常用配置元件介绍总结之后置处理器 8.后置处理器8.1.CSS/JQuery提取器8.2.JSON JMESPath Extractor8.3.JSON提取器8.4.正则表达式提取器8.5.边界提取器8.5.Debug PostProcessor8.6.XPath2 Extractor8.7.XPath提取器8.8.结果状态处理器 8.后置处理…

基于Java Springboot旅游信息推荐系统

一、作品包含 源码数据库设计文档万字全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA 数据库&#xff1a;MySQL8.0…

基础网络安全知识

1.ctfhub技能树 1.1 Web-SQL注入 Web-SQL注入-整数型 && 字符型 && MySQL结构 参考&#xff1a;5.9.6MySql注入 Web-SQL注入-报错注入 step1: 查库名 ?id1 and extractvalue(1,concat(0x7e,database(),0x7e))-- step2: 查看表名 ?id1 and extractvalue(1…

01-Ajax入门与axios使用、URL知识

欢迎来到“雪碧聊技术”CSDN博客&#xff01; 在这里&#xff0c;您将踏入一个专注于Java开发技术的知识殿堂。无论您是Java编程的初学者&#xff0c;还是具有一定经验的开发者&#xff0c;相信我的博客都能为您提供宝贵的学习资源和实用技巧。作为您的技术向导&#xff0c;我将…

iStore OS 插件的手动安装与特殊卸载

有些插件在iStore 中并没有展示,因此需要手动安装,手动安装无法通过前端彻底卸载,本文提供方法和流程。 1.插件手动安装 1.1地址 github 项目地址根据自己需求选择。本人以x86_64 为主。 https://github.com/AUK9527/Are-u-ok/tree/main/x86 点击后下载得到run安装包 1…

neo4j desktop基本入门

下载安装不在赘述&#xff0c;本文只记述一些neo4j的基本入门操作 连接本地neo4j数据库 1. 点击ADD添加连接 端口一般是7687 账户名和密码忘记了&#xff0c;可以通过neo4j web&#xff08;默认为neo4jneo4j://localhost:7687/neo4j - Neo4j Browser&#xff09;重置密码 AL…

ElasticSearch的Python Client测试

一、Python环境准备 1、下载Python安装包并安装 https://www.python.org/ftp/python/3.13.0/python-3.13.0-amd64.exe 2、安装 SDK 参考ES官方文档: https://www.elastic.co/guide/en/elasticsearch/client/index.html python -m pip install elasticsearch一、Client 代…

强化学习入门笔记(Reinforcement Learning,RL) 强推!

由于本人的近期研究方向涉及到强化学习&#xff0c;本科时已经学习过了&#xff0c;但是感觉还是有些概念和算法没有学懂学透&#xff0c;所以想重新系统性的学习一下&#xff0c;记录了整个学习过程&#xff0c;而且对当时没有理解不是特别深刻的内容有了一些更加深刻的理解&a…

redis 原理篇 26 网络模型 Redis是单线程的吗?为什么使用单线程

都是学cs的&#xff0c;有人月薪几万&#xff0c;有人月薪几千&#xff0c;哎&#xff0c; 相信 边际效用&#xff0c; 也就是说&#xff0c; 随着技术提升的越来越多&#xff0c;薪资的提升比例会更大 一个月几万&#xff0c;那肯定是高级开发了&#xff0c; 一个月几千&…

UE4 Cook 从UAT传递参数给UE4Editor

需求 一句Cook的命令如下&#xff1a; ${EnginePath}/Engine/Build/BatchFiles/RunUAT.sh BuildCookRun -project${ClientPath}/${ProjectName}.uproject -noP4 -platformIOS -cooksinglepackage -client -clientconfig${CookConfig} -iterate -skipbuild -nocompile -NoMutex…

jmeter基础05_第1个http请求

本节课使用网站“httpbin.org”进行基础的http请求全流程。 请求获取httpbin.org的首页&#xff1a; 请求方法&#xff1a;GET URL&#xff1a;http://httpbin.org 参数&#xff1a;无 1、操作步骤 ① 打开jmeter&#xff1a;命令行窗口输入“jmeter”并回车。 ② 添加线程组…