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

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...

爬虫基础学习day2

# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...