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

数据结构-时间复杂度/空间复杂度

  Hello,好久没有更新了哦,已经开始学习数据结构了,这篇文章呢就是对刚学数据结构所接触到的时间复杂度进行一个分享哦,如果有错误之处,大家记得拍拍我哦~

既然要讨论时间/空间复杂度,那我们就得知道时间/空间复杂度是什么,那到底什么是时间复杂度,什么是空间复杂度呢?

一、时间复杂度

时间复杂度:它是一个函数,这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用O()来表示,不包括这个函数的低价项和首项系数。一个算法所花费的时间与其中语句的执行次数成正比例,那么,算法中的基本操作的执行次数就是算法的时间复杂度。

理解:算法的时间复杂度它是一个函数,其定量的描述了该算法的运行时间。但是,仔细一想,一个算法执行所消耗的时间,从理论上来说的话,它是不可以算出来的,只有在你把程序放在机器上跑起来时,我们才能够知道该算法在整个执行的过程中所消耗的时间。

说这么多,其实用一句话总结:就是找到某条基本语句与问题规模N之间的数学表达式,也就是算出了该算法的时间复杂度

注:时间复杂度通常用O()来表示。

常见的有:O(1),O(n),O(logn),O(nlogn),O(n^2)等

下面详细介绍一下:

O(1):常数时间复杂度。这类可以说明算法的执行时间不随输入规模的增大而增长。比如,数组的访问,哈希表的查找(后期会更)。

O(n):线性时间复杂度。这类可以说明算法的执行时间随输入规模的增大而增长,其增长速度与输入规模成正比。比如,数组的遍历,简单查找等。

O(logn):对数时间复杂度。这类可以说明算法的执行时间随输入规模的增大而增长。

O(nlogn):线性对数时间复杂度。这类可以说明算法的执行时间随着输入规模的增大而增长,但增长速度比线性快。比如,归并排序,快速排序等。

O(n^2):平方时间复杂度。这类可以说明算法的执行速度随着输入规模的增大而增长,且增长速度很快。比如,冒泡排序,选择排序等。

说明:这里提到的排序后面会更新的,大家在这里先听听哦,这里主要是掌握对时间复杂度的理解。

举个例子:

大家看这段代码:

// 请计算一下Func1中++count语句总共执行了多少次?
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--){++count;}printf("%d\n", count);
}

实际上当我们掌握这个知识点并且有个很多的练习时,我们就知道,在计算时间复杂度的时候,我们其实并不一定要计算精确的执行次数,我们只需要计算知道大概的执行次数就可以啦~ 提高一个知识肯定就会有新的知识点的出现,这里我们就使用大O的渐进表示法。
接下来我们就介绍一下大O的渐进表示法的规则和该注意的点:
大O符号:用于描述函数渐进行为的数学符号。
规则:
(1)用常数1取代运行时间中的所有加法常熟。
(2)在修改后的运行次数函数中,只保留最高阶项。
(3)如果最高阶项存在但不是1时,这时就去除与这个项目相乘的常数,,从而得到的结果就是大O阶。
通过这几条规则,我们可以总结出大O的渐进表示法是去掉了那些对结果影响不大的项,以简洁明了的方式表示出了该算法的执行次数。
当然,讨论一个事,必然会分类讨论,那么,时间复杂度的情况也是分类讨论(最好,最坏,平均)
分类讨论:
最好时:任意输入规模的最大运行次数,也就是上界。
最坏时:任意输入规模的最小运行次数,也就是下界。
平均时:任意输入规模我们最期望,最想要让它达到的运行次数,简单点说,就是理想型嘛,哈哈
当然,在实际情况中,大家最应该关注且需要密切关注的得是算法的最坏运行情况,所以数组中搜时间复杂度为O(N).

算法的时间复杂度分为:

(1)最好时间复杂度:指的是算法计算量可能达到的最小值。

(2)最坏时间复杂度:指的是算法计算量可能达到的最大值。

(3)平均时间复杂度:指算法在所有可能情况下,按照输入实例以等概率出现时,算法计算量的加权平均值。

时间复杂度主要衡量一个算法的运行速度的快慢,空间复杂度主要衡量一个算法运行所需要的额外空间。

二、空间复杂度

空间复杂度:也是一个数学表达式,是对一个算法在运行过程当中临时占用存储空间大小的量度,换句话说,也就是额外占取的空间的大小。空间复杂度不是程序占用了多少空间,因为讲这个其实没有多大意义,所以空间复杂度算的其实是变量的个数。当然,都是复杂度嘛,空间复杂度和时间复杂度的规则基本大差不差,同样使用大O渐进表示法。
注:空间复杂度基本上是O(1)/O(N),其他不怎么常见哦~
接下来举例子说明哦~
a:计算阶乘的时间复杂度
阶乘递归的空间复杂度是O(N);

b:计算冒泡排序的空间复杂度

// 计算BubbleSort的空间复杂度?
void BubbleSort(int* a, int n)
{assert(a);for (int end = n; end > 0; --end){int exchange = 0;for (int i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

思路:重复走过要排序的数列,一次比较两个元素,如果它们的顺序不太对劲,就把它们错误的顺序交换过来。这个“工作”是重复的进行知道不再需要交换,换句话说这个数列已经排序完成了。

这里,冒泡排序的辅助变量只是一个临时变量,而且其不会随着排序规模的扩大而因此改变,所以它的空间复杂度为O(1)。

   不过,这里要提一嘴的是,对于算法的性能,需要从时间和空间的使用情况来评价。一个好的算法,应该是同时具备时间复杂度和空间复杂度都较低的特性,但是,从实际情况来看的话,对于某个算法问题,要想使得时间复杂度和空间复杂度都优化是蛮困难的。如果说降低时间复杂度的话,那么往往会是它的空间复杂度提高。所以,在通常情况下,在算法设计的过程当中,一般会通过空间换时间的做法,牺牲一部分计算机存储空间,从而来提升整个算法的运行速度。

好啦,关于数据结构中关于 时间复杂度和空间复杂度的介绍先到这里啦,后期有时间的话还会举一些更为详细的例子和大家一起进步~

看到这里,支持一下小编叭~ 如果有错误之处,大家记得评论区留言吖~

相关文章:

数据结构-时间复杂度/空间复杂度

Hello&#xff0c;好久没有更新了哦&#xff0c;已经开始学习数据结构了&#xff0c;这篇文章呢就是对刚学数据结构所接触到的时间复杂度进行一个分享哦&#xff0c;如果有错误之处&#xff0c;大家记得拍拍我哦~ 既然要讨论时间/空间复杂度&#xff0c;那我们就得知道时间/空…...

英语写作中“展示”、“表明”demonstrate、show、indicate、illustrate的用法

一、demonstrate、show、indicate在论文写作中主要用法是&#xff1a;demonstrate/show/indicate 从句&#xff1a; Sb./Sth. demonstrates/shows/indicates that ……从句中一般表达事实、观点和结论等。 例句&#xff1a; The authors demonstrated/showed/indicated that…...

Redis的java客户端

在Redis官网中提供了各种语言的客户端&#xff0c;地址&#xff1a;https://redis.io/resources/clients/ redis的java客户端 https://redis.io/resources/clients/#java 1.jedis使用 引入依赖 <dependency><groupId>redis.clients</groupId><artifac…...

Android环境配置笔记

文章目录 一、各环境文档二、参考 一、各环境文档 Gradle官方的兼容性文档&#xff1a;Java Compatibility 更新日期&#xff1a;2023.9.12 Android Gradle插件版本&#xff1a;Android Gradle Plugin 二、参考 参考文章&#xff1a;Android问题记录...

element-table 行的拖拽更改顺序(无需下载sortableJs

样例展示&#xff1a;vueelement 通过阅读element文档我们发现element并不提供拖拽相关的api 本博客通过element提供的行类名 注册函数 实现行与行的拖拽 1.设置el-table 的行样式类名 这里是用的是 function <el-table:data"outputData":row-class-name&qu…...

Docker部署jenkins

目录 一、jenkins原理二、Docker部署jenkins1.下载jenkins镜像文件2.查看下载的jenkins镜像3.创建Jenkins挂载目录并授权权限4.创建并启动Jenkins容器5.查看jenkins是否启动成功6.查看docker容器日志7.配置镜像加速8.访问Jenkins页面&#xff0c;输入ip地址加上9000端口9.获取管…...

从0到1学会Git(第三部分):Git的远程仓库链接与操作

写在前面:前面两篇文章我们已经学会了git如何在本地进行使用&#xff0c;这篇文章将讲解如何将本地的git仓库和云端的远程仓库链接起来并使用 为什么要使用远程仓库:因为我们需要拷贝我们的代码给别人以及进行协同开发&#xff0c;就需要有一个云端仓库进行代码的存储和同步&a…...

虚拟机Ubuntu操作系统常用终端命令(1)(详细解释+详细演示)

虚拟机Ubuntu操作系统常用终端命令 本篇讲述了Ubuntu操作系统常用的三个功能&#xff0c;即归档&#xff0c;软链接和用户管理方面的相关知识。希望能够得到大家的支持。 文章目录 虚拟机Ubuntu操作系统常用终端命令二、使用步骤1.归档1.1创建档案包1.2还原档案包1.3归档并压缩…...

redis实战-redis实现异步秒杀优化

秒杀优化-异步秒杀思路 未优化的思路 当用户发起请求&#xff0c;此时会请求nginx&#xff0c;nginx会访问到tomcat&#xff0c;而tomcat中的程序&#xff0c;会进行串行操作&#xff0c;分成如下几个步骤 1、查询优惠卷 2、判断秒杀库存是否足够 3、查询订单 4、校验是否是一…...

Python爬虫-IP隐藏技术与代理爬取

前言 在进行爬虫程序开发和运行时&#xff0c;常常会遇到目标网站的反爬虫机制&#xff0c;最常见的就是IP封禁&#xff0c;这时需要使用IP隐藏技术和代理爬取。 一、IP隐藏技术 IP隐藏技术&#xff0c;即伪装IP地址&#xff0c;使得爬虫请求的IP地址不被目标网站识别为爬虫。…...

二刷力扣--链表

链表 链表类型&#xff1a; 单链表&#xff08;可以访问后面的一个节点&#xff09; 双链表&#xff08;可以访问前后节点&#xff09; 循环链表&#xff08;最后一个节点指向首节点&#xff09; 在Python中定义单链表节点&#xff1a; class ListNode:def __init__(self, v…...

返回值加const ,为了不拷贝得到成员的值,但被赋值的左值也要const

1. getA 函数返回值 什么都不加&#xff0c;也改不了c里面a的指针指向 why&#xff1f;返回成员变量时&#xff0c;会复制一下。 返回成员变量时&#xff0c;一般会赋值一下没有RVO_地摊书贩的博客-CSDN博客 2. getA 函数返回值 加了引用&#xff0c; 就没有复制 3. getA 函数…...

本地如何使用HTTPS进行调试

在现代前端开发中&#xff0c;HTTPS已经成为不可或缺的一部分&#xff0c;因为它在保护用户数据和确保网站安全性方面发挥着关键作用。然而&#xff0c;有时在本地开发过程中启用HTTPS可能会变得有些复杂。在本文中&#xff0c;我们将介绍如何轻松地在本地进行HTTPS调试&#x…...

观察者模式:对象之间的订阅机制

欢迎来到设计模式系列的第十三篇文章&#xff01;在之前的文章中&#xff0c;我们学习了许多常用的设计模式&#xff0c;今天我们将介绍观察者模式&#xff0c;它是一种行为型设计模式&#xff0c;用于定义对象之间的一对多依赖关系&#xff0c;当一个对象的状态发生变化时&…...

【1462. 课程表 IV】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 你总共需要上 numCourses 门课&#xff0c;课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite &#xff0c;其中 prerequisites[i] [ai, bi] 表示如果你想选 bi 课程&#xff0c;你…...

Kerberos 身份验证

简介 Kerberos 是一种由 MIT&#xff08;麻省理工大学&#xff09;提出的一种基于加密 Ticket 的身份认证协议。它旨在通过使用密钥加密技术为客户端/服务器应用程序提供强身份验证&#xff0c;用于验证用户或主机的标识。。 适用范围&#xff1a;Windows Server 2022、Window…...

R语言贝叶斯METROPOLIS-HASTINGS GIBBS 吉布斯采样器估计变点指数分布分析泊松过程车站等待时间...

原文链接&#xff1a;http://tecdat.cn/?p26578 指数分布是泊松过程中事件之间时间的概率分布&#xff0c;因此它用于预测到下一个事件的等待时间&#xff0c;例如&#xff0c;您需要在公共汽车站等待的时间&#xff0c;直到下一班车到了&#xff08;点击文末“阅读原文”获取…...

通付盾入选2023年度“上市苗圃工程”重点企业

近日&#xff0c;2023年度苏州工业园区企业上市苗圃工程认定名单公示&#xff0c;江苏通付盾科技有限公司成功入选园区“上市苗圃工程”重点企业。 2023年第一批次苗圃企业认定结果&#xff1a; 企业上市苗圃工程 上市企业是衡量地方综合经济实力的重要标尺&#xff0c;也是区…...

SpringMVC之文件上传下载

SpringMVC是一个基于Java的Web框架&#xff0c;它提供了一套用于构建Web应用程序的开发模型。在SpringMVC中&#xff0c;文件上传和下载是常见的功能之一。 SpringMVC文件上传和下载的介绍&#xff1a; 介绍文件上传&#xff1a; 在SpringMVC中&#xff0c;文件上传功能可以通…...

嵌入式IDE(2):KEIL中SCF分散加载链接文件详解和实例分析

在上一篇文章IAR中ICF链接文件详解和实例分析中&#xff0c;我通过I.MX RT1170的SDK中的内存映射关系&#xff0c;分析了IAR中的ICF链接文件的语法。对于MCU编程所使用的IDE来说&#xff0c;IAR和Keil用得比较多&#xff0c;所以这一篇文章就来分析一下Keil的分散文件.scf(scat…...

Linux防火墙常用操作及端口开放

Linux防火墙常用操作及端口开放 1.查看防火墙状态 firewall-cmd --state 2.开启防火墙 systemctl start firewalld.service 3.开启指定端口 firewall-cmd --zonepublic --add-port3306/tcp --permanent firewall-cmd --zonepublic --add-port6379/tcp --permanent 显示success表…...

[JAVAee]Linux上的javax.mail报错

我们把在window写的项目部署到Linux上的Tomcat时,如果发现使用不了了,该如何找到错误呢?找到报错的地方在哪呢? 在Linux环境下来到Tomcat目录下的logs目录,输入: tail -f catalina.out -n 500 tail 就是把文件的末尾几行读取到终端上,并会持续刷新 -f 循环读取 catalina.ou…...

开学季|校园迎新哪家强?VR全景来导航

九月开学迎新季&#xff0c;各大高校的迎新活动开展的如火如荼&#xff0c;随着科技的不断进步&#xff0c;高校为了更好的开展迎新活动&#xff0c;让新生们尽快熟悉新的校园和生活&#xff0c;会利用VR全景技术带领着新生进行校园游览&#xff0c;给予新生们巨大便利的同时&a…...

el-checkbox-group限制勾选数量

<!--* Description: 视频监控 页面* Author: mhf* Date: 2023-08-15 13:26:33 --> <template><div class"videoSurveillance"><el-row :gutter"24"><el-col :span"4"><div class"videoSurveillance-left&…...

【JavaScript】WebAPI入门到实战

文章目录 一、WebAPI背景知识1. 什么是WebAPI&#xff1f;2. 什么是API&#xff1f; 二、DOM基本概念三、获取元素三、事件初识1. 点击事件2. 键盘事件 四、操作元素1. 获取/修改元素内容2. 获取/修改元素属性3. 获取/修改表单元素属性4. 获取/修改样式属性 五、操作节点1. 新增…...

奥康的高尔夫鞋,圈不住投资者的心

文 | 螳螂观察 作者 | 青月 鞋服行业终于熬过了“寒冬”&#xff0c;2023年行业景气度开始逐步回暖。 东方财富Choice数据显示&#xff0c;截至8月17日&#xff0c;已有28家鞋帽服装类上市公司发布了2023年中期业绩预告或快报&#xff0c;其中&#xff0c;9家预增&#xff0…...

vue2配置环境变量并且nginx运行成功

需求&#xff1a;我在vue项目配置了生产环境和开发环境&#xff0c;之后通过proxy代理的方式把地址转发到真实的服务器地址上用于请求接口&#xff0c;之后把项目打包后上传到nginx上&#xff0c;之后接口报错404&#xff0c;但是本地运行是可以访问的&#xff0c;找了很久终于…...

Java+Swing形成GUI图像界面

一、Swing 简介 Swing 主要用来开发 GUI 程序,GUI(Graphical User Interface)即图形用户界面。Java 中针对 GUI 设计提供了丰富的类库,这些类分别位于 java.awt 和 java.swing 中,简称 AWT 和 Swing ;其中,AWT(Abstract Window Toolkit)是抽象窗口工具包,是 Java 平…...

编辑距离 -- 动规

72. 编辑距离 给出动规的两种常见实现形式&#xff1a;自顶向下、自底向上&#xff0c;前者一般借助递归函数备忘录实现&#xff0c;后者通常基于dp数组实现。 class MinDistance:"""72. 编辑距离https://leetcode.cn/problems/edit-distance/""&quo…...

douyin【商品抢购js脚本】

文章目录 前言订阅须知知识点源码前言 脚本主要用来实现抢购douyin商城、直播间秒杀商品等一系列商品 订阅须知 订阅后,只提供js源代码,不提供教学,请根据源码自行抓包知识点 1、在查询串插入一个固定的键rstr   2、对查询串进行按键排序并取值,对空格和+进行转义为a …...

上海专业网站建设流程/龙岗seo优化

【摘要】 看起来很简单的集合运算放在大数据的场景下&#xff0c;如果还想获得高性能就需要充分了解数据特征和计算特征才能设计出高效算法。充分利用序运算就是一种好办法&#xff01;交并差是常见的集合运算&#xff0c;SQL 中对应的 intersect/union/minus 计算也很简单。不…...

织梦系统如何做网站地图/软文发稿公司

在数组中就地移除value的元素&#xff0c;并且不用管移除后的顺序稳定性。 大致思路&#xff1a; 如果要前移来删除数组元素的话要O(n^2)。 这里的方法是——两个指针&#xff08;发现两个指针在“就地处决”真的很重要诶...&#xff09;&#xff0c;一个一直指向最后一个元…...

建工网论坛/seo基础课程

测试机器学习算法 现在你对机器学习算法的分类已经有了一个大体的了解&#xff0c;但在更进一步了解每个算法的细节之前&#xff0c;你还需要对如何测试机器学习算法有一个大体的认识。 在大多数情况下&#xff0c;将会出现以下三类数据&#xff1a;训练数据集&#xff08;trai…...

做网站设计师/点击器原理

鲜嫩多汁的玉米&#xff0c;最近老妈是成袋往家里领&#xff0c;每天早餐的时候&#xff0c;她都会煮上2个&#xff0c;清甜又美味。可是再好吃的东西&#xff0c;老是一个味&#xff0c;吃到后面&#xff0c;大家都不怎么爱吃了。玉米是一种营养非常好的&#xff0c;最常吃的粗…...

网站开发模式分为/长春seo网站排名

06-9-27在网吧里&#xff0c;任何时间都会有人在吃饭&#xff0c;有人在睡觉&#xff0c;有人在玩。不论是清晨&#xff0c;中午&#xff0c;还是深夜&#xff0c;都有一些人挺不住了&#xff0c;他们用疲惫无神的双眼仔细注视着屏幕&#xff0c;仿佛创作中的马克思。他们是铁人…...

网站免费推广大全/专业网站制作

Python urllib Python是一种高级编程语言&#xff0c;在软件开发的各个领域都得到了广泛应用。在Web编程中&#xff0c;Python的urllib模块可帮助您通过HTTP、FTP和其他协议访问网络资源。在本文中&#xff0c;我们将讨论Python urllib模块的基础知识。 什么是urllib&#xf…...