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

数据结构:算法(特性,时间复杂度,空间复杂度)

目录

  • 1.算法的概念
  • 2.算法的特性
    • 1.有穷性
    • 2.确定性
    • 3.可行性
    • 4.输入
    • 5.输出
  • 3.好算法的特质
    • 1.正确性
    • 2.可读性
    • 3.健壮性
    • 4.高效率与低存储需求
  • 4.算法的时间复杂度
    • 1.事后统计的问题
    • 2.复杂度表示的计算
      • 1.加法规则
      • 2.乘法规则
      • 3.常见函数数量级比较
  • 5.算法的空间复杂度
    • 1.程序的内存需求
    • 2.例题
    • 3.函数调用(递归)带来的内存开销

1.算法的概念

算法(Algorithm)是对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。

2.算法的特性

1.有穷性

一个算法必须总在执行有穷步之后结束,且每一步都可在有穷时间内完成。
算法必须是有穷的,而程序可以是无穷的

2.确定性

算法中每条指令必须有确切的含义,对于相同的输入只能得出相同的输出

3.可行性

算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

4.输入

一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合。

5.输出

一个算法有一个或多个输出,这些输出是与输入有着某种特定关系的量。

3.好算法的特质

1.正确性

算法应能够正确地解决求解问题。

2.可读性

算法应具有良好的可读性,以帮助人们理解。

3.健壮性

输入非法数据时,算法能适当地做出反应或进行处理,而不会产生莫名其妙的输出结果。

4.高效率与低存储需求

即算法执行省时、省内存:时间复杂度低、空间复杂度低。

4.算法的时间复杂度

事前预估算法时间开销T(n)与问题规模n的关系(T表示“time”)

  • 最坏时间复杂度:最坏情况下算法的时间复杂度。
  • 平均时间复杂度:所有输入示例等概率出现的情优下,算法的期望运行时间。
  • 最好时间复杂度:最好情况下算法的时间复杂度。

1.事后统计的问题

①和机器性能有关,如:超级计算机v.s.单片机
②和编程语言有关,越高级的语言执行效率越低
③和编译程序产生的机器指令质量有关
④有些算法是不能事后再统计的,如:导弹控制算法

2.复杂度表示的计算

1.加法规则

多项相加,只保留最高阶的项,且系数变为1。

2.乘法规则

多项相乘,都保留。

3.常见函数数量级比较

在这里插入图片描述

①顺序执行的代码只会影响常数项,可以忽略。
②只需挑循环中的一个基本操作分析它的执行次数与n的关系即可。
③如果有多层嵌套循环,只需关注最深层循环循环了几次。

5.算法的空间复杂度

1.程序的内存需求

①若无论问题规模怎么变,算法运行所需的内存空间都是固定的常量,
算法空间复杂度为s(n)= o(1),则称该算法为原地工作:算法所需的内存空间为常量。
②只需关注存储空间大小与问题规模相关的变量。

2.例题

在这里插入图片描述

3.函数调用(递归)带来的内存开销

一般情况,空间复杂度等于递归调用的深度。
注:有的算法各层函数所需存储空间不同,分析方法略有区别。

相关文章:

数据结构:算法(特性,时间复杂度,空间复杂度)

目录 1.算法的概念2.算法的特性1.有穷性2.确定性3.可行性4.输入5.输出 3.好算法的特质1.正确性2.可读性3.健壮性4.高效率与低存储需求 4.算法的时间复杂度1.事后统计的问题2.复杂度表示的计算1.加法规则2.乘法规则3.常见函数数量级比较 5.算法的空间复杂度1.程序的内存需求2.例…...

SaaS 出海,如何搭建国际化服务体系?(一)

防噎指南:这可能是你看到的干货含量最高的 SaaS 出海经验分享,请准备好水杯,放肆食用(XD。 当越来越多中国 SaaS 企业选择开启「国际化」副本,出海便俨然成为国内 SaaS 的新角斗场。 LigaAI 观察到,出海浪…...

数据结构与算法-(7)---栈的应用拓展-前缀表达式转换+求值

🌈write in front🌈 🧸大家好,我是Aileen🧸.希望你看完之后,能对你有所帮助,不足请指正!共同学习交流. 🆔本文由Aileen_0v0🧸 原创 CSDN首发🐒 如…...

泛型的使用

泛型是一种Java编程语法&#xff0c;它允许我们编写支持多种数据类型的通用类、方法和接口。使用泛型可以使代码更通用、更灵活、更健壮&#xff0c;并提高代码的重用性。 在Java中&#xff0c;泛型的语法使用尖括号<>和类型参数来定义。例如&#xff0c;我们可以定义一…...

docker导致远程主机无法访问,docker网段冲突导致主机网络异常无法访问

背景&#xff1a; 公司分配的虚拟机是172网段的&#xff0c;在上面部署了docker、docker-compose、mysql、redis,程序用docker-compose管理&#xff0c;也平稳运行了一个多周&#xff0c;某天用FinalShell连主机重启docker容器&#xff0c;忽然断开连接&#xff0c;然后虚拟机就…...

Python的web自动化学习(三)Selenium的显性、隐形等待

引言&#xff1a; WebDriver的显性等待和隐形等待是用于在测试过程中等待元素加载或操作完成的两种等待方式。了解此两种方式是为后面自动化找到适合的方法去运用 显性等待&#xff08;Explicit Wait&#xff09; 显性等待是通过使用WebDriverWait类和ExpectedConditions类来…...

Linux--文件操作

1.什么是文件 对于文件来说&#xff0c;文件文件内容文件属性&#xff1b;对于文件来说&#xff0c;只有两种操作&#xff0c;对内容的修改和对文件属性的修改&#xff0c;这就是文件的范畴。 对于存放在磁盘上的文件&#xff0c;我们需要通过进程来进行访问&#xff0c;访问文…...

硬件知识积累 RS422接口

1. RS422 基本介绍 EIA-422&#xff08;过去称为RS-422&#xff09;是一系列的规定采用4线&#xff0c;全双工&#xff0c;差分传输&#xff0c;多点通信的数据传输协议。它采用平衡传输采用单向/非可逆&#xff0c;有使能端或没有使能端的传输线。和RS-485不同的是EIA-422不允…...

项目经验分享|openGauss 陈贤文:受益于开源,回馈于开源

开源之夏 项目经验分享 2023 #08 # 关于 openGauss 社区 openGauss是一款开源关系型数据库管理系统&#xff0c;采用木兰宽松许可证v2发行。openGauss内核深度融合华为在数据库领域多年的经验&#xff0c;结合企业级场景需求&#xff0c;持续构建竞争力特性。同时openGauss也是…...

实时检测并识别视频中的汽车车牌

对于基于摄像头监控的安全系统来说,识别汽车牌照是一项非常重要的任务。我们可以使用一些计算机视觉技术从图像中提取车牌,然后我们可以使用光学字符识别来识别车牌号码。在这里,我将引导您完成此任务的整个过程。 要求: import cv2import numpy as npfrom skimage impor…...

使用 pyspark 进行 Clustering 的简单例子 -- KMeans

K-means算法适合于简单的聚类问题,但可能不适用于复杂的聚类问题。此外,在使用K-means算法之前,需要对数据进行预处理和缩放,以避免偏差。 K-means是一种聚类算法,它将数据点分为不同的簇或组。Pyspark实现的K-means算法基本遵循以下步骤: 随机选择K个点作为初始质心。根…...

LeetCode75——Day22

文章目录 一、题目二、题解 一、题目 1657. Determine if Two Strings Are Close Two strings are considered close if you can attain one from the other using the following operations: Operation 1: Swap any two existing characters. For example, abcde -> aec…...

【SOC基础】单片机学习案例汇总 Part1:电机驱动、点亮LED

&#x1f4e2;&#xff1a;如果你也对机器人、人工智能感兴趣&#xff0c;看来我们志同道合✨ &#x1f4e2;&#xff1a;不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 &#x1f4e2;&#xff1a;文章若有幸对你有帮助&#xff0c;可点赞 &#x1f44d;…...

【HTML】HTML基础知识扫盲

1、什么是HTML&#xff1f; HTML是超文本标记语言&#xff08;Hyper Text Markup Language&#xff09;是用来描述网页的一种语言 注意&#xff1a; HTML不是编程语言&#xff0c;而是标记语言 HTML文件也可以直接称为网页&#xff0c;浏览器的作用就是读取HTML文件&#xff…...

【Mybatis-Plus】常见的@table类注解

目录 引入Mybatis-Plus依赖 TableName 当实体类的类名在转成小写后和数据库表名相同时 当实体类的类名在转成小写后和数据库表名不相同时 Tableld TableField 当数据库字段名与实体类成员不一致 成员变量名以is开头&#xff0c;且是布尔值 ​编辑 成员变量名与数据库关…...

Android WMS——操作View(七)

上一篇文章我们将 view 传递给 ViewRootImpl 进行操作,这里我们主要分析 ViewRootImpl 对 View 进行操作。在正式分析之前我们先来介绍以下 View。 一、View介绍 最开始学习 View 的时候最先分析的是它的布局(LinearLayout、FrameLayout、TableLayout、RelativeLayout、Abso…...

算法__数组排序_冒泡排序直接选择排序快速排序

文章目录 冒泡排序算法说明代码实现 直接选择排序算法说明代码实现 快速排序算法说明代码实现 本篇主要讲解数组排序相关的三种算法&#xff0c;冒泡排序&#xff0c;直接排序和快速排序。 冒泡排序 算法说明 在数组中依次比较相邻的两个元素&#xff0c;当满足左侧大于右侧时…...

ByteBuffer的原理和使用详解

ByteBuffer是字节缓冲区&#xff0c;主要用户读取和缓存字节数据&#xff0c;多用于网络编程&#xff0c;原生的类&#xff0c;存在不好用&#xff0c;Netty采用自己的ByteBuff&#xff0c;对其进行了改进 1.ByteBuffer的2种创建方式 1.ByteBuffer buf ByteBuffer.allocate(i…...

【MySql】10- 实践篇(八)

文章目录 1. 用动态的观点看加锁1.1 不等号条件里的等值查询1.2 等值查询的过程1.3 怎么看死锁&#xff1f;1.4 怎么看锁等待&#xff1f;1.5 update 的例子 2. 误删数据后怎么办?2.1 删除行2.2 误删库/表2.3 延迟复制备库2.4 预防误删库 / 表的方法2.4.1 账号分离2.4.2 制定操…...

【三方登录-Apple】iOS 苹果授权登录(sign in with Apple)之开发者配置一

记录一下sign in with Apple的开发者配置 前言 关于使用 Apple 登录 使用“通过 Apple 登录”可让用户设置帐户并使用其Apple ID登录您的应用程序和关联网站。首先使用“使用 Apple 登录”功能启用应用程序的App ID 。 如果您是首次启用应用程序 ID 或为新应用程序启用应用程序…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...