数据结构:算法(特性,时间复杂度,空间复杂度)
目录
- 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编程语法,它允许我们编写支持多种数据类型的通用类、方法和接口。使用泛型可以使代码更通用、更灵活、更健壮,并提高代码的重用性。 在Java中,泛型的语法使用尖括号<>和类型参数来定义。例如,我们可以定义一…...
docker导致远程主机无法访问,docker网段冲突导致主机网络异常无法访问
背景: 公司分配的虚拟机是172网段的,在上面部署了docker、docker-compose、mysql、redis,程序用docker-compose管理,也平稳运行了一个多周,某天用FinalShell连主机重启docker容器,忽然断开连接,然后虚拟机就…...
Python的web自动化学习(三)Selenium的显性、隐形等待
引言: WebDriver的显性等待和隐形等待是用于在测试过程中等待元素加载或操作完成的两种等待方式。了解此两种方式是为后面自动化找到适合的方法去运用 显性等待(Explicit Wait) 显性等待是通过使用WebDriverWait类和ExpectedConditions类来…...
Linux--文件操作
1.什么是文件 对于文件来说,文件文件内容文件属性;对于文件来说,只有两种操作,对内容的修改和对文件属性的修改,这就是文件的范畴。 对于存放在磁盘上的文件,我们需要通过进程来进行访问,访问文…...
硬件知识积累 RS422接口
1. RS422 基本介绍 EIA-422(过去称为RS-422)是一系列的规定采用4线,全双工,差分传输,多点通信的数据传输协议。它采用平衡传输采用单向/非可逆,有使能端或没有使能端的传输线。和RS-485不同的是EIA-422不允…...
项目经验分享|openGauss 陈贤文:受益于开源,回馈于开源
开源之夏 项目经验分享 2023 #08 # 关于 openGauss 社区 openGauss是一款开源关系型数据库管理系统,采用木兰宽松许可证v2发行。openGauss内核深度融合华为在数据库领域多年的经验,结合企业级场景需求,持续构建竞争力特性。同时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
📢:如果你也对机器人、人工智能感兴趣,看来我们志同道合✨ 📢:不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 📢:文章若有幸对你有帮助,可点赞 👍…...
【HTML】HTML基础知识扫盲
1、什么是HTML? HTML是超文本标记语言(Hyper Text Markup Language)是用来描述网页的一种语言 注意: HTML不是编程语言,而是标记语言 HTML文件也可以直接称为网页,浏览器的作用就是读取HTML文件ÿ…...
【Mybatis-Plus】常见的@table类注解
目录 引入Mybatis-Plus依赖 TableName 当实体类的类名在转成小写后和数据库表名相同时 当实体类的类名在转成小写后和数据库表名不相同时 Tableld TableField 当数据库字段名与实体类成员不一致 成员变量名以is开头,且是布尔值 编辑 成员变量名与数据库关…...
Android WMS——操作View(七)
上一篇文章我们将 view 传递给 ViewRootImpl 进行操作,这里我们主要分析 ViewRootImpl 对 View 进行操作。在正式分析之前我们先来介绍以下 View。 一、View介绍 最开始学习 View 的时候最先分析的是它的布局(LinearLayout、FrameLayout、TableLayout、RelativeLayout、Abso…...
算法__数组排序_冒泡排序直接选择排序快速排序
文章目录 冒泡排序算法说明代码实现 直接选择排序算法说明代码实现 快速排序算法说明代码实现 本篇主要讲解数组排序相关的三种算法,冒泡排序,直接排序和快速排序。 冒泡排序 算法说明 在数组中依次比较相邻的两个元素,当满足左侧大于右侧时…...
ByteBuffer的原理和使用详解
ByteBuffer是字节缓冲区,主要用户读取和缓存字节数据,多用于网络编程,原生的类,存在不好用,Netty采用自己的ByteBuff,对其进行了改进 1.ByteBuffer的2种创建方式 1.ByteBuffer buf ByteBuffer.allocate(i…...
【MySql】10- 实践篇(八)
文章目录 1. 用动态的观点看加锁1.1 不等号条件里的等值查询1.2 等值查询的过程1.3 怎么看死锁?1.4 怎么看锁等待?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 或为新应用程序启用应用程序…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...
