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

学习数据结构(2)空间复杂度+顺序表

1.空间复杂度

(1)概念

空间复杂度也是一个数学表达式,表示一个算法在运行过程中根据算法的需要额外临时开辟的空间。 空间复杂度不是指程序占用了多少bytes的空间,因为常规情况每个对象大小差异不会很大,所以空间复杂度算的是变量的个数。 空间复杂度的计算规则基本和时间复杂度类似,也使用大O渐进表示法

函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定

(2)示例

例1:计算BubbleSort的空间复杂度

函数栈帧在编译时已经确定了,只需要关注函数在运行时额外申请的空间,有size_t end、size_t i、int exchange 三个额外创建的变量,F(N)=3,故空间复杂度为O(1)

例2:计算Fac的空间复杂度

递归算法的空间复杂度=单次递归的空间复杂度*递归次数,每调用一次递归函数开辟一个函数栈帧,这里调用了N次,空间复杂度为O(N)

2.常见复杂度对比

(这是作者在百度上找的图)

3.关于复杂度的算法题

提交代码1(循环k次,每一次先保存数组最后一位元素,循环将数组前numsSize-1个元素向后移动一位,将最后一位元素值赋给数组第一个元素):

分析可知,这段代码的时间复杂度为O(N^2),空间复杂度为O(N),代码效率不高

提交代码2(创建一个新数组,将原数组中后k个元素移到新数组的前k位,将元素组中的前numSize-k个元素移到新数组的后numSize-k位,再将新数组的每一位对应赋给原数组的每一位):

分析可知,这段代码的时间复杂度为O(N),空间复杂度为O(N),相对代码1效率提高了

提交代码3(编写一个逆置函数,将数组前numSize-k个元素逆置,再将数组后k个元素逆置,最后将数组整体逆置):

分析可知,这段代码的时间复杂度为O(N),空间复杂度为O(1)

4.线性表

线性表是n个具有相同特性的数据元素的有限序列,常见的线性表:顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构,在物理上通常以数组和链式结构的形式存储

5.顺序表

(1)概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储,顺序表的底层结构是数组,对数组的封装,实现了常用的增删改查等接口

(2)静态顺序表和动态顺序表

静态顺序表:使用定长数组储存元素

typedef int SLDataType;
#define N 7;
typedef struct Seqlist
{SLDataType a[N];//定长数组int size;//有效数据个数
}SL;

或另写一行代码重命名:

typedef int SLDataType;
#define N 7;
struct Seqlist
{SLDataType a[N];//定长数组int size;//有效数据个数
};
typedef struct SeqList SL;

动态顺序表:创建指针变量,按需申请内存

typedef int SLDataType;
typedef struct Seqlist
{SLDataType* a;int size;//有效数据个数int capacity;//空间容量
}SL;

相关文章:

学习数据结构(2)空间复杂度+顺序表

1.空间复杂度 (1)概念 空间复杂度也是一个数学表达式,表示一个算法在运行过程中根据算法的需要额外临时开辟的空间。 空间复杂度不是指程序占用了多少bytes的空间,因为常规情况每个对象大小差异不会很大,所以空间复杂…...

C语言复习

1.进制 三要素:数位(第几位) 基数 位权(当前位对应的值) 二进制:B 八进制:O 十进制:D 十六进制:X 0和1 111 /072 10 …...

Qt监控系统辅屏预览/可以同时打开4个屏幕预览/支持5x64通道预览/onvif和rtsp接入/性能好

一、前言说明 在监控系统中,一般主界面肯定带了多个通道比如16/64通道的画面预览,随着电脑性能的增强和多屏幕的发展,再加上现在监控摄像头数量的增加,越来越多的用户希望在不同的屏幕预览不同的实时画面,一个办法是打…...

ubuntu22安装issac gym记录

整体参考:https://blog.csdn.net/Yakusha/article/details/144306858 安装完成后的整体版本信息 ubuntu:22.04内核:6.8.0-51-generic显卡:NVIDIA GeForce RTX 3050 OEM显卡驱动:535.216.03cuda:12.2cudnn&…...

IDEA工具下载、配置和Tomcat配置

1. IDEA工具下载、配置 1.1. IDEA工具下载 1.1.1. 下载方式一 官方地址下载 1.1.2. 下载方式二 官方地址下载:https://www.jetbrains.com/idea/ 1.1.3. 注册账户 官网地址:https://account.jetbrains.com/login 1.1.4. JetBrains官方账号注册…...

Three.js实战项目02:vue3+three.js实现汽车展厅项目

文章目录 实战项目02项目预览项目创建初始化项目模型加载与展厅灯光加载汽车模型设置灯光材质设置完整项目下载实战项目02 项目预览 完整项目效果: 项目创建 创建项目: pnpm create vue安装包: pnpm add three@0.153.0 pnpm add gsap初始化项目 修改App.js代码&#x…...

动态规划——斜率优化DP

题目清单 acwing300.任务安排1 状态表示f[i]: 集合:完成前i个任务且第i个任务为最后一个批次最后一个任务的方案。 属性:min 状态计算: f [ i ] m i n { f [ j ] s u m t [ i ] ∑ j 1 i w [ u ] s ∑ j 1 n w [ i ] } f[i]min\{f[j…...

【深度之眼cs231n第七期】笔记(三十一)

目录 强化学习什么是强化学习?马尔可夫决策过程(MDP)Q-learning策略梯度SOTA深度强化学习 还剩一点小尾巴,还是把它写完吧。(距离我写下前面那行字又过了好几个月了【咸鱼本鱼】)(汗颜&#xff…...

【云安全】云原生-K8S-简介

K8S简介 Kubernetes(简称K8S)是一种开源的容器编排平台,用于管理容器化应用的部署、扩展和运维。它由Google于2014年开源并交给CNCF(Cloud Native Computing Foundation)维护。K8S通过提供自动化、灵活的功能&#xf…...

SpringBoot中Excel表的导入、导出功能的实现

文章目录 一、easyExcel简介二、Excel表的导出2.1 添加 Maven 依赖2.2 创建导出数据的实体类4. 编写导出接口5. 前端代码6. 实现效果 三、excel表的导出1. Excel表导入的整体流程1.1 配置文件存储路径 2. 前端实现2.1 文件上传组件 2.2 文件上传逻辑3. 后端实现3.1 文件上传接口…...

Spark入门(Python)

目录 一、安装Spark 二、Spark基本操作 一、安装Spark pip3 install pyspark 二、Spark基本操作 # 导入spark的SparkContext,SparkConf模块 from pyspark import SparkContext, SparkConf # 导入os模块 import os # 设置PYSPARK的python环境 os.environ[PYSPARK_PYTHON] &…...

Daemon进程创建过程

Daemon创建过程: 1、fork,创建子进程。退出父进程。 2、setsid,创建新会话。脱离原会话、进程组、控制终端。 再次fork,与终端完全脱离。第二次fork的意义???? 先脱离原父进程&#…...

在sortablejs的拖拽排序情况下阻止input拖拽事件

如题 问题 在vue3的elementPlus的table中,通过sortablejs添加了行拖拽功能,但是在行内会有输入框,此时拖拽输入框会触发sortablejs的拖拽功能 解决 基于这个现象,我怀疑是由于拖拽事件未绑定而冒泡到后面的行上从而导致的拖拽…...

C++初阶—string类

第一章:为什么要学习string类 1.1 C语言中的字符串 C语言中,字符串是以\0结尾的一些字符的集合,为了操作方便,C标准库中提供了一些str系列的库函数,但是这些库函数与字符串是分离开的,不太符合OOP的思想&…...

C# 提取PDF表单数据

目录 使用工具 C# 提取多个PDF表单域的数据 C# 提取特定PDF表单域的数据 PDF表单是一种常见的数据收集工具,广泛应用于调查问卷、业务合同等场景。凭借出色的跨平台兼容性和标准化特点,PDF表单在各行各业中得到了广泛应用。然而,当需要整合…...

算法刷题Day28:BM66 最长公共子串

题目链接,点击跳转 题目描述: 解题思路: 方法一:暴力枚举 遍历str1的每个字符x,并在str2中寻找以相同元素x为起始的最长字符串。记录最长的公共子串及其长度。 代码实现: def LCS(self, str1: str, st…...

论文阅读笔记:MambaOut: Do We Really Need Mamba for Vision?

论文阅读笔记:MambaOut: Do We Really Need Mamba for Vision? 1 背景2 创新点3 方法4 模块4.1 Mamba适合什么任务4.2 视觉识别任务是否有很长的序列4.3 视觉任务是否需要因果token混合模式4.4 关于Mamba对于视觉的必要性假设 5 效果 论文:https://arxi…...

HarmonyOS:ForEach:循环渲染

一、前言 ForEach接口基于数组类型数据来进行循环渲染,需要与容器组件配合使用,且接口返回的组件应当是允许包含在ForEach父容器组件中的子组件。例如,ListItem组件要求ForEach的父容器组件必须为List组件。 API参数说明见:ForEa…...

Python3 【函数】项目实战:5 个新颖的学习案例

Python3 【函数】项目实战:5 个新颖的学习案例 本文包含5编程学习案例,具体项目如下: 简易聊天机器人待办事项提醒器密码生成器简易文本分析工具简易文件加密解密工具 项目 1:简易聊天机器人 功能描述: 实现一个简易…...

XSS 漏洞全面解析:原理、危害与防范

目录 前言​编辑 漏洞原理 XSS 漏洞的危害 检测 XSS 漏洞的方法 防范 XSS 漏洞的措施 前言 在网络安全的复杂版图中,XSS 漏洞,即跨站脚本攻击(Cross - Site Scripting),是一类极为普遍且威胁巨大的安全隐患。随着互…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...