数据结构:算法(特性,时间复杂度,空间复杂度)
目录
- 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 或为新应用程序启用应用程序…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
