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

【数据结构与算法】第1课—算法复杂度

news 2026/2/10 22:33:56

文章目录

  • 1. 数据结构
  • 2. 算法
  • 3. 算法效率
  • 4. 算法复杂度
  • 5. 算法时间复杂度
    • 5.1 大O的渐进表示法
    • 5.2 时间复杂度示例
  • 6. 空间复杂度
    • 6.1 练习1
    • 6.2 练习2
    • 6.3 练习3

1. 数据结构

  • 数据结构是计算机存储、组织数据的方式，指相互之间存在一种和多种特定关系的数据元素的集合，常见的有线性表、树、图、哈希等

2. 算法

  • 算法：就是制定一个良好的计算过程，取一个或一组值作为输入，并产生一个或一组值作为输出
  • 简单来讲，算法就是一系列的计算步骤，用来将输入数据转化为输出结果

3. 算法效率

  我们先来看个简单的例子
在这里插入图片描述
  这个时候可能就满足不了，那么我们如何去判断一个代码的好坏呢？

4. 算法复杂度

  • 衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的
  • 时间复杂度主要衡量一个算法运行速度快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间

5. 算法时间复杂度

  • 为什么不用程序执行速度的快慢来作为判断一个算法的好坏呢？
  • 这是因为相同的程序在不同的计算机、不同的编译器上、乃至同一台计算机上执行速度都有所不同，并且时间只能在程序编写好后才可以进行测试，因此它不会直接用来作为衡量程序好坏的标准
  • 计算机科学规定了，作为衡量一个算法好坏的算法时间复杂度是一个表达式T(N),它用来计算程序的执行次数
  • 如果一个算法a程序的T(N)=N,另一个算法b程序的T(N)=N^2,那么算法a的效率一定优于算法b

在这里插入图片描述

5.1 大O的渐进表示法

  • 前面我们讲过，T(N)表达式中可能存在对它影响很小的变量和常量，因此我们需要抓大头来表示程序的变化趋势，因此就引入了大O的渐进表示法
  • 大O表示规则：
  • 时间复杂度表达式T(N)中，只保留高阶项，去掉低阶项，用来表示程序执行次数变化的趋势
  • 如果高阶项存在不是1，不将与高阶项相关的常数系数计算在内，因为随着N不断变大，常数系数对结果影响也不大
  • T(N)中如果高阶项就是常数，那么直接写成O(1),用1来代替所有的常数，其中1并不表示程序只执行一次，而是表示它与执行算法所需的时间与输入数据的数量或大小无关

在这里插入图片描述

5.2 时间复杂度示例

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  • 通过上述例子可以看出，大O渐进表示法一般关注的是算法的上界，也就是最坏的运行情况

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

6. 空间复杂度

  • 函数运行时所需要的栈空间（存储参数、局部变量、一些寄存器信息等）在编译器期间已经确定好了，因此空间复杂度主要考虑函数在运行时额外申请的空间
  • 空间复杂度也用大O表示法

在这里插入图片描述

在这里插入图片描述

6.1 练习1

在这里插入图片描述

6.2 练习2

  • 创建新的数组，将k个数据放入新的数组中，再将剩下的数据放进去
  • 空间复杂度O(N)

在这里插入图片描述

6.3 练习3

  • 空间复杂度O(1)

在这里插入图片描述

相关文章：

【数据结构与算法】第1课—算法复杂度

文章目录 1. 数据结构2. 算法3. 算法效率4. 算法复杂度5. 算法时间复杂度5.1 大O的渐进表示法5.2 时间复杂度示例 6. 空间复杂度6.1 练习16.2 练习26.3 练习3 1. 数据结构 数据结构是计算机存储、组织数据的方式，指相互之间存在一种和多种特定关系的数据元素的集合&…...

编程日记 2024/10/17 22:19:51

利用高德API获取整个城市的公交路线并可视化（五）

如果说我比别人看得更远些，那是因为我站在了巨人的肩上。——牛顿 参考：使用高德API获取公交线路数据，无需代码_实时公交api-CSDN博客 记录于2024年10月，因数据获取受网站更新策略等影响可能会失效，故记录写作时间，同时拾人牙慧，优化了后半部分数据直接导出为csv和shp…...

编程日记 2024/10/17 22:15:46

DNS：互联网域名系统的核心

什么是 DNS？ DNS（Domain Name System，域名系统）是互联网的一项基础服务，它负责将人类容易记忆的域名（如 www.example.com）转换成计算机可以识别的 IP 地址（如 192.0.2.1&#xff09…...

编程日记 2024/10/17 22:14:45

小猿口算炸鱼脚本

目录 写在前面： 一、关于小猿口算： 二、代码逻辑 1.数字识别 2.答题部分 三、代码分享： 补充：软件包下载 写在前面： 最近小猿口算已经被不少大学生攻占，小学生直呼有挂。原本是以为大学生都打着本…...

编程日记 2024/10/17 22:10:42

浅谈云原生--微服务、CICD、Serverless、服务网格

往期推荐 浅学React和JSX-CSDN博客 一文搞懂大数据流式计算引擎Flink【万字详解，史上最全】-CSDN博客 一文入门大数据准流式计算引擎Spark【万字详解，全网最新】_大数据 spark-CSDN博客 目录 1. 云原生概念和特点 2. 常见云模式 3. 云对外提供服务的…...

编程日记 2024/10/17 22:09:40

android app执行shell命令视频课程补充android 10/11适配-千里马android

(https://blog.csdn.net/learnframework/article/details/120103471) https://blog.csdn.net/learnframework/article/details/120103471 hi，有学员在学习跨进程通信专题课程时候，在实战app执行一个shell命令的项目时候，对课程本身的android …...

编程日记 2024/10/17 22:08:35

C++笔记-UTF8和UTF8-dom的区别

在文件格式上，UTF-8 和 UTF-8-BOM 是两种不同的编码方式，其中 UTF-8-BOM 包含字节顺序标记（BOM），而 UTF-8 则不包含。 UTF-8： UTF-8 是一种以字节为单位的可变长度字符编码，常用于以字节为单位…...

编程日记 2024/10/17 22:07:32

“探索Adobe Photoshop 2024：订阅方案、成本效益分析及在线替代品“

设计师们对Adobe Photoshop这款业界领先的图像编辑软件肯定不会陌生。如果你正考虑加入Photoshop的用户行列，可能会对其价格感到好奇。Photoshop的价值在于其强大的功能，而它的价格也反映了这一点。下面，我们就来详细了解一下Adobe Photoshop…...

编程日记 2024/10/17 22:06:29

网页复制粘贴助手，Chrome网页复制插件(谷歌浏览器复制插件)

一款解决网页限制复制问题的插件，当你遇到限制复制粘贴和右键的网页是不是很头痛？安装这个插件后，点下插件按钮就能解决了 碰到这种情况 也是非常头疼 chrome拓展-chrome插件-强制复制 当我们浏览网页的时候，看到感兴趣的内容就…...

编程日记 2024/10/17 22:05:28

【C++刷题】力扣-#118-杨辉三角

题目描述 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。在杨辉三角中，每个数是它正上方两个数的和。 示例 示例 1: 输入: numRows 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2: 输入: numRows 1 输出: [[1]]题解 这个问题…...

编程日记 2024/10/17 22:03:26

Linux下的环境变量

目录 1.引言 1.1bash的部分工作 1.2main函数也有参数 1.3我们可以通过给main函数传入不同的参数，让同一份代码实现不同的功能 1.4先认识一个环境变量PATH，帮助Linux找到指令程序的地址 2.环境变量 2.1环境变量的概念 2.2见见其他的环境变量 2…...

编程日记 2024/10/17 22:02:25

Edge论文的创新点

创新点及其来源 1. 从灰度边缘重建RGB图像的方法（EdgRec） 基于的方法：传统的重建方法，如使用自动编码器或生成模型来重建正常样本的图像，并通过对原始图像和重建图像的比较来检测异常。 重建过程： 训练阶…...

编程日记 2024/10/17 22:01:23

‌ComfyUI 高级实战：实现华为手机的AI消除功能

大家好，我是每天分享AI应用的萤火君！ 不知道大家是否还记得华为 Pura 70的「AI消除」事件，当时使用 华为Pura 70 系列手机的智能消除功能时，该功能可以被用来消除照片中女性胸口处的衣物，这一功能曾引发广泛的关注和伦…...

编程日记 2024/10/17 21:59:21

我记得我曾喜欢过冬天

写在前面 1316 字 | 感触 | 世界 | 情感 | 体验 | 经历 | 想法 | 认知 正文 晚上出门，起电单车，很冷。冻得有些发抖。下车，我第一时间和珍发了消息。 我说，居然在四川感受到了哈尔滨的温度。 哈尔滨的夏天很热，但哈尔…...

编程日记 2024/10/17 21:58:15

最新夜间数据集发布LoLI-Street: 33000帧数据，涵盖19000个目标

最新夜间数据集发布LoLI-Street: 33000帧数据，涵盖19000个目标 Abstract 低光照图像增强（LLIE）对于许多计算机视觉任务至关重要，包括目标检测、跟踪、分割和场景理解。尽管已有大量研究致力于提高在低光照条件下捕捉的低质量图像…...

编程日记 2024/10/17 21:57:13

反向传播算法与随机搜索算法的比较

反向传播算法与随机搜索算法的比较 在这篇文章中，我们将通过一个简单的线性回归问题来比较反向传播算法和随机搜索算法的性能。我们将使用Python代码来实现这两种算法，并可视化它们的梯度下降过程。 反向传播算法 反向传播算法是深度学习和神经网络训…...

编程日记 2024/10/17 21:52:06

【PDF文件】默认被某种软件打开，如何进行修改？

当有时下载某种软件后，电脑中的PDF文件就默认由该种软件打开，每次需要右键选择打开方式才能选择需要的其他软件打开。如下图所示。 修改方法： （1）点击电脑的“设置”，选择应用 （2）…...

编程日记 2024/10/17 21:48:02

Kaggle Python练习：字符串和字典（Exercise: Strings and Dictionaries）

文章目录 问题：搜索特定单词并定位思路代码实现官方代码代码解析 更进一步 问题：搜索特定单词并定位 一位研究人员收集了数千篇新闻文章。但她想将注意力集中在包含特定单词的文章上。完成以下功能以帮助她过滤文章列表。 您的函数应满足以下条件&…...

编程日记 2024/10/17 21:46:00

React(四) 事件总线，setState的原理，PureComponent优化React性能,ref获取类组件与函数组件

文章目录 一、全局事件总线二、setState的原理1. 为什么要使用setState修改数据2. setState的三种用法(1) 基本使用(2) 传入回调函数(3) setState是一个异步调用 3. setState为什么要设置成异步 二、PureComponent优化性能1. React的diff算法以及Key的优化(扩展)(1) diff算法(2…...

编程日记 2024/10/17 21:41:57

Java学习-JVM

目录 1. 基本常识 1.1 JVM是什么 1.2 JVM架构图 1.3 Java技术体系 1.4 Java与JVM的关系 2. 类加载系统 2.1 类加载器种类 2.2 执行顺序 2.3 类加载四个时机 2.4 生命周期 2.5 类加载途径 2.6 双亲委派模型 3. 运行时数据区 3.1 运行时数据区构成 3.2 堆 3.3 栈…...

编程日记 2024/10/17 21:40:55

【杂谈】-递归进化：人工智能的自我改进与监管挑战

递归进化：人工智能的自我改进与监管挑战 文章目录 递归进化：人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管？3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

编程新知 2025/12/9 0:22:01

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

编程新知 2026/2/8 20:42:41

智慧医疗能源事业线深度画像分析（上）

引言 医疗行业作为现代社会的关键基础设施，其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入，智慧医疗能源事业线应运而生，致力于通过创新技术与管理方案，重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

编程新知 2026/2/10 4:40:33

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

编程新知 2026/1/31 6:04:01

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

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

编程新知 2026/1/31 23:23:23

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理）

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

编程新知 2026/2/3 8:20:06

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

编程新知 2025/9/24 16:25:00

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

编程新知 2026/1/25 7:20:01

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

编程新知 2026/2/9 20:16:17

数据结构第5章：树和二叉树完全指南（自整理详细图文笔记）

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

编程新知 2026/2/4 20:23:50