当前位置: 首页 > 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),是一类极为普遍且威胁巨大的安全隐患。随着互…...

Wan2.2-I2V-A14B部署教程:混合云架构下边缘节点视频生成能力下沉

Wan2.2-I2V-A14B部署教程:混合云架构下边缘节点视频生成能力下沉 1. 镜像概述与核心价值 Wan2.2-I2V-A14B私有部署镜像是一款专为文生视频场景优化的解决方案,特别适合需要在边缘节点部署视频生成能力的企业用户。这个镜像最大的特点是"开箱即用&…...

人工智能与光学系统的深度融合:大模型在光学设计与成像中的应用~!

Nature重磅!超表面硬件融合物理AI!开创定量相位成像新范式!https://mp.weixin.qq.com/s/M5151pe1Kns5s89Hy9eEAA点击此链接查看详情! 专题三:大模型光学设计专题 学习目标: 本课程旨在系统性培养学生利用…...

SWIFT报文格式规范:从字符约束到金融交易安全的深度解析

1. SWIFT报文格式规范的核心价值 第一次接触SWIFT报文时,我被那些看似简单的字母代号震撼到了——谁能想到,像"2!n"这样简单的符号组合,竟然承载着全球金融系统的运转规则?在跨境汇款中输错一个字符可能导致资金滞留数周…...

C语言函数返回值的设计哲学与实践

1. C语言函数返回值的本质与设计哲学在嵌入式开发领域摸爬滚打十几年,我见过太多因为函数返回值设计不当导致的"血案"。记得刚入行时调试一个串口通信模块,就因为误判了第三方库的返回值逻辑,整整浪费了两天时间。C语言的函数返回值…...

基于GA - XGBoost的时间序列预测:抑制过拟合与参数优化

基于遗传算法优化算法优化XGBoost(GA-XGBoost)的时间序列预测 GA-XGBoost时间序列 采用交叉验证抑制过拟合问题 优化参数为迭代次数、最大深度和学习率 matlab代码,注:暂无Matlab版本要求 -- 推荐 2016B 版本及以上 注:采用 XGBoost 工具箱&a…...

Vue-Super-Flow隐藏玩法:不画图,只填空!手把手教你打造可配置的流程图答题组件

Vue-Super-Flow隐藏玩法:不画图,只填空!手把手教你打造可配置的流程图答题组件 在Vue生态中,流程图工具通常被用来构建复杂的可视化编辑界面。但你是否想过,这些工具还能用来做些什么?本文将带你探索一个全…...

League-Toolkit:颠覆式英雄联盟客户端增强工具的全攻略

League-Toolkit:颠覆式英雄联盟客户端增强工具的全攻略 【免费下载链接】League-Toolkit An all-in-one toolkit for LeagueClient. Gathering power 🚀. 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit League-Toolkit是一款基于官…...

忍者像素绘卷效果对比:亮色像素美学 vs 传统暗调像素艺术表现力

忍者像素绘卷效果对比:亮色像素美学 vs 传统暗调像素艺术表现力 1. 作品概述 忍者像素绘卷是一款基于Z-Image-Turbo深度优化的图像生成工作站,它将忍者文化与16-Bit复古游戏美学完美融合。这款工具最显著的特点是采用了全新的"亮色像素"界面…...

硬件解放:开源工具突破设备限制的深度探索指南

硬件解放:开源工具突破设备限制的深度探索指南 【免费下载链接】OpenCore-Legacy-Patcher Experience macOS just like before 项目地址: https://gitcode.com/GitHub_Trending/op/OpenCore-Legacy-Patcher 当你的设备被厂商贴上"过时"标签&#x…...

通过配置驱动前端页面的实现方法

通过配置驱动前端页面的实现方法 配置驱动开发(Configuration-Driven Development, CDD)是一种通过外部配置而非硬编码来控制应用行为的开发模式。在前端领域,这种模式可以显著提升页面灵活性和可维护性。以下是具体实现方案: 理解…...