数据结构-时间复杂度与空间复杂度详解

文章目录

    • 算法效率
    • 时间复杂度
      • 概念
      • 计算
      • 例1
      • 例2
      • 例3
      • 补充
      • 例4
    • 空间复杂度
      • 例1
      • 例2


算法效率

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

时间复杂度

概念

在计算机科学中,算法的是时间复杂度是一个函数,它定量的描述了该算法运行的时间,但是理论上是不能够算出来的,因为同一个算法在不同机器上的运行时间是不一样的,这取决于机器的效率。又因为一个算法花费的时间和和语句的执行次数成正比,所以我们可以通过算执行次数来代替算时间。也就是说算法中基本操作的执行次数即时间复杂度

计算

实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大0的渐进表示法
大0符号(Big O notation):是用于描述函数渐进行为的数学符号。推导大0阶方法:
1、用常数1取代运行时间中的所有加法常数,即常数次数都用O(1)表示.
2、在修改后的运行次数函数中,只保留最高阶项,如:N^2+N+4>>O(N ^2)
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大0阶,如:2N>>O(N)
4、有n次和常数次时常数次舍掉如:N+3>>O(N)

例1

简单循环
代码:
在这里插入图片描述
上面代码中一共执行了 5+3=8次,根据大O渐进法来说所有的常数都表示为O(1).
所以这个代码的时间复杂度为O(1).

例2

还是举个简单的例子来计算
代码:在这里插入图片描述
上面的代码一共执行了n+5
根据大O渐进法来说这里的 5 舍掉,所以这里的时间复杂度为O(n)

例3

冒泡排序(不懂的话可以看我主页哦,有详解)
在这里插入图片描述
冒泡排序是这里是一个等差数列,n n-1 n-1……1–(N+1)N/2=(N*N-N)/2,根据大O渐进法来说这里的1/2,和N都要舍掉
所以这里的时间复杂度为O(N^2)

补充

在这里插入图片描述

例4

二分查找法(不懂的话可以看我主页哦,有详解)
在这里插入图片描述
二分查找每查找一次都折一半,那我们将过程反过来列式 >>相当于每找一次就乘2 222*2=n,**假设查找x次>>2^x=n>>lon2N(这里2为底)也可以写成lonN
所以二分查找法的
时间复杂度为O(lonN)**

有的童鞋说是不是一层循环时间复杂度就是O(n),两层就是O(N^2)捏,其实这是错的

从二分查找法就可以看出,二分查找有一层循环但是时间复杂度不为O(n)
这是要具体分析算法才能得出的

空间复杂度

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

例1

给数组赋值
在这里插入图片描述
这里用了三个额外的变量p(指针变量),i,r,再根据大O渐进法来讲常数都用O(1)表示
所以这里的空间复杂度为O(1);

例2

交换数组

在这里插入图片描述
这里创建额外的数组用了n个空间,还有i,r,p(指针变量)三个变量,一共n+3,
根据大O渐进法这里的空间复杂度为O(n)

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

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

相关文章

Delicious Retouch5 for mac(PS磨皮插件DR5白金版)

Delicious Retouch5是一款强大的Photoshop插件,专为专业摄影师和摄影爱好者设计,提供一系列高级修图工具,帮助用户更快速、更有效地进行照片修饰和美化。其主要功能包括皮肤美容、人像润色、头发修饰、修复工具等,并配备定制化画笔…

海外邮件接收延迟、接收不到怎么办?U-Mail邮件网关来了

随着经济全球化的发展,很多国内企业开始踏足海外市场,电子邮件就成为了国内企业与海外客户沟通交流的主要渠道。然而海外邮件接收延迟、接收不到等问题成为了困扰企业与海外客户沟通的一大阻碍,导致客户邮件回复不及时,询盘邮件接…

新版本!飞凌嵌入式RK3568系列开发板全面支持Debian 11系统

飞凌嵌入式OK3568-C/OK3568J-C开发板现已全面支持Debian 11系统,新系统的加持能为用户提供主控新选择,并为开发者带来更多开发便利! Debian系统作为一种广受欢迎和信赖的开源操作系统,以其稳定性、可靠性和开放性而闻名&#xff0…

2013年5月23日 Go生态洞察:高级Go并发模式分析

🌷🍁 博主猫头虎(🐅🐾)带您 Go to New World✨🍁 🦄 博客首页——🐅🐾猫头虎的博客🎐 🐳 《面试题大全专栏》 🦕 文章图文…

OpenELA 正式公开 Enterprise Linux 源代码

导读近日消息,在红帽(Red Hat)宣布不再对外公开 Red Hat Enterprise Linux(RHEL)源代码之后,同属 Linux 领域的甲骨文、SUSE 及 CIQ 宣布成立了 Open Enterprise Linux Association(OpenELA&…

xstream实现xml和java bean 互相转换

目录 pom引用java bean 类XML 转换工具类测试类执行结果注意问题 Java中实现XML和Bean的转换的方式或插件有以下几种: JAXB(Java Architecture for XML Binding):JAXB是Java SE的一部分,可以将Java对象与XML文档相互转…

Linux 图形界面配置RAID

目录 RAID 1 配置 RAID 5配置 , RAID 配置起来要比 LVM 方便,因为它不像 LVM 那样分了物理卷、卷组和逻辑卷三层,而且每层都需要配置。我们在图形安装界面中配置 RAID 1和 RAID 5,先来看看 RAID 1 的配置方法。 RAID 1 配置 配置 RAID 1…

开源项目datavines内存泄漏问题分析

应用程序开启JMX java -Dspring.profiles.activemysql -Dcom.sun.management.jmxremote.port1099 -Dcom.sun.management.jmxremote.sslfalse -Dcom.sun.management.jmxremote.authenticatefalse -Djava.rmi.server.hostname127.0.0.1 -jar dataVines.jar 通过jdk自带工具&…

数据结构第四课 -----线性表之队列

作者前言 🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂 ​🎂 作者介绍: 🎂🎂 🎂 🎉🎉&#x1f389…

使用geek卸载windows软件,干净彻底

我们在电脑上安装软件,以及在使用软件的过程中,会产生一些程序文件、注册表项和临时文件等,用来支持软件的正常使用,都是正常现象。 但是,在卸载软件时,很多软件的卸载程序,并不能完全清除软件…

excel中正态分布函数NORM.DIST和NORMDIST,以及它们之间的区别

NORM.DIST和NORMDIST的区别 NORM.DIST和NORMDIST函数都可以返回正态分布的概率密度、或者正态累积分布。 根据微软官网上的说法,NORMDIST函数已经不建议使用了,它已经被一个或者几个新的函数代替(例如NORM.DIST),这些…

RabbitMQ-高级篇-黑马程序员

代码: 链接: https://pan.baidu.com/s/1nQBIgB_SbzoKu_XMWZ3JoA?pwdaeoe 提取码:aeoe 在昨天的练习作业中,我们改造了余额支付功能,在支付成功后利用RabbitMQ通知交易服务,更新业务订单状态为已支付。 但…

Python数据结构:集合(set)详解

1.集合的概念 在Python中,集合(Set)是一种无序、不重复的数据类型,它的实现基于哈希表,是由唯一元素组成的。集合中不允许有重复的元素,即相同元素只能出现一次。Python中的集合类似于数学中的集合&#xf…

你是想被ChatGPT改变,还是改变软件开发的未来?丨IDCF

人工智能技术的发展,正在深刻地改变着我们的生活和工作方式。在软件工程领域,ChatGPT作为一种新兴的人工智能技术,正在逐渐地被应用到软件开发的各个环节中。那么,ChatGPT对每个人的影响是什么呢? 一、对软件开发人员…

LockBit3.0的字符串解密方法

LockBit 与大多数勒索黑客团体一样以勒索软件即服务 (RaaS) 模式运行,该组织于 2019 年 9 月首次被观察到,此后发展为了今年最主要的勒索软件团伙,甚至超过了Conti、Hive等其他知名团体。据泄露数据站点的数据统计表明,LockBit占2022年第一季度所有与勒索软件相关的泄露事件…

使用Pandas进行数据读写的简易教程

Pandas是一个功能强大且广泛使用的Python库。它提供了一种简单而灵活的方式来读取和写入各种数据格式,包括CSV、Excel、SQL数据库等。本文将介绍如何使用Pandas进行数据的读取和写入操作,帮助你快速上手并高效地处理数据。 一、安装和导入pandas 首先&…

NovelD: A Simple yet Effective Exploration Criterion论文笔记

NovelD:一种简单而有效的探索准则 1、Motivation 针对稀疏奖励环境下的智能体探索问题,许多工作中采用各种内在奖励(Intrinsic Reward)设计来指导困难探索环境中的探索 ,例如: ICM:基于前向动力学模型的好奇心驱动探索RND&…

【LeetCode】每日一题 2023_11_15 K 个元素的最大和(脑筋急转弯+数学)

文章目录 刷题前唠嗑K 个元素的最大和题目描述代码与解题思路 结语 刷题前唠嗑 LeetCode? 启动!!! 首先声明一点啊,这个脑筋急转弯的题目标签可不是我想的啊,这个是 LeetCode 官方给这道题标注的啊 K 个元素的最大和…

spring cloud alibaba之nacos

spring cloud nacos 安装和启动nacos # 解压nacos安装包 # tar -zvxf nacos-server-1.4.1.tar.gz# nacos默认是以集群的模式启动,此处先用单机模式 # cd /usr/local/mysoft/nacos/bin # sh startup.sh -m standalone# nacos 日志 # tail -f /usr/local/mysoft/na…