2.1算法的时间复杂度与空间复杂度
本篇博客介绍算法的时间复杂度与空间复杂度
一、算法效率
算法好坏从时间和空间两个维度衡量
二、时间复杂度
1.概念
时间复杂度是算法中基本操作的执行次数,定量描述了算法的运行时间
2.注意
(1)时间复杂度是偏保守的估计量,可理解为最低的预期
(2)时间复杂度是一个数量级,表征大概执行次数,采用大O渐进表示法
- 如果是常数次计算,时间复杂度为O(1)
- 在运行次数函数中,只保留次数最高的那一项
- 要省略最高阶项前面的常数

(3)时间复杂度实际上是一个函数f(x),注意与平时编程时调用的函数进行区分,是算法精确的执行次数
3.例子
(1)冒泡排序的时间复杂度
void BubbleSort(int* a, int n)
{ assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; }
}

(2)二分查找的时间复杂度
int BinarySearch(int* a, int n, int x)
{ assert(a); int begin = 0; int end = n-1; while (begin <= end) { int mid = begin + ((end-begin)>>1); if (a[mid] < x) begin = mid+1; else if (a[mid] > x) end = mid-1; else return mid; } return -1;
}

注意:只有以2为底的对数才可以简写成logN
(3)递归函数的时间复杂度
long long Fac(size_t N)
{ if(0 == N) return 1; return Fac(N-1)*N;
}

三、空间复杂度
1.概念
空间复杂度是算法运行过程中临时占用存储空间大小的量度,算的是变量的个数,研究额外申请的空间
2.例子
long long Fac(size_t N)
{ if(N == 0) return 1; return Fac(N-1)*N;
}
解析:从Fac(N)到Fac(0)共调用Fac()函数N+1次,数量级是N,因此空间复杂度为O(N)
相关文章:
2.1算法的时间复杂度与空间复杂度
本篇博客介绍算法的时间复杂度与空间复杂度 一、算法效率 算法好坏从时间和空间两个维度衡量 二、时间复杂度 1.概念 时间复杂度是算法中基本操作的执行次数,定量描述了算法的运行时间 2.注意 (1)时间复杂度是偏…...
Linux VSFTP 部署与配置
一、VSFTP 简介与应用 VSFTP(Very Secure FTP Daemon)是一款功能强大、安全可靠的FTP服务器软件,广泛应用于Linux/Unix系统中。它提供了高效的文件传输服务,并具备诸多安全特性,如用户认证、权限控制、SSL/TLS加密等。…...
【Docker】Docker Consul
docker consul Docker Consul 是一个用于服务发现和配置的开源工具,它是 HashiCorp 公司推出的一个项目。Consul 提供了一个中心化的服务注册和发现系统,可以帮助开发人员轻松地在 Docker 容器和集群之间进行服务发现和配置管理。 Consul 使用基于 HTT…...
diamond安装与使用
1.前言 diamond是一款用于蛋白质和翻译后DNA搜索的序列比对工具,专为大规模序列数据的高性能分析设计。其主要特点包括: - 与BLAST相比,蛋白质和翻译后DNA的成对比对速度快100倍至10000倍。 2. 参考 https://github.com/bbuchfink/diamond …...
flume--数据从kafka到hdfs发生错误
解决: #1.将flume自带的依赖删除 mv /opt/installs/flume1.9/lib/guava-11.0.2.jar /opt/installs/flume1.9/lib/guava-11.0.2.jar.bak #2.将hadoop的依赖发送到flume下 cp /opt/installs/hadoop3.1.4/share/hadoop/common/lib/guava-27.0-jre.jar /opt/installs/f…...
Android笔试面试题AI答之Kotlin(14)
文章目录 64. Kotlin中定义函数还是属性场景?使用属性的场景使用函数的场景示例 65. 阐述Kotlin中变量初始化有几种?其中lateinit、by lazy、delegates.notNull有什么区别 ?Kotlin中变量初始化的几种方式lateinit、by lazy、Delegates.notNull的区别 66. Kotlin中…...
博弈论,CF 1600E - Array Game
目录 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 1600E - Array Game 二、解题报告 1、思路分析 记最长递增前缀长度为L&a…...
win10安装docker,打包python、java然后centos执行镜像
一、win10安装Docker Desktop docker官网(需要魔法)下载:https://www.docker.com/products/docker-desktop/ 安装方法参考:https://blog.csdn.net/beautifulmemory/article/details/137970794 下载完毕后界面安装,不勾…...
【数据结构入门】二叉树之堆的实现
文章目录 前言一、树1.1 树的概念1.2 树的相关概念 二、二叉树2.1 二叉树的概念2.2 特殊的二叉树2.3 二叉树的性质 三、堆3.1 堆的概念3.2 堆的性质3.3 堆的存储3.4 堆的实现3.4.1 堆的初始化3.4.2 堆的销毁3.4.1 堆向上调整算法3.4.2 堆向下调整算法3.4.3 堆的创建3.4.4 堆的插…...
智能微气候:精准调控背后的算法革命
( 于景鑫 国家农业信息化工程技术研究中心)当人工智能遇见现代农业,会擦出怎样的火花?随着数字农业、智慧农业的蓬勃发展,人工智能技术正以前所未有的速度渗透到农业生产的方方面面。其中,以深度学习为代表的前沿算法,尤其是大语言模型(LLM),正在成为驱…...
eNSP 华为交换机链路聚合
华为交换机链路聚合 链路聚合好处: 1、提高带宽 2、链路冗余 SW_2: <Huawei>sys [Huawei]sys SW_2 [SW_2]vlan batch 10 20 [SW_2]int g0/0/4 [SW_2-GigabitEthernet0/0/4]port link-type access [SW_2-GigabitEthernet0/0/4]port default vl…...
编译器揭秘
从上世纪50年代开始,编程语言五花八门,编译器和解释器层出不穷。此处只列出常见编程语言的编译器和解释器信息,不常见的编程语言有单独文章介绍。 C/C cc 此处代表Unix C编译器,其他平台可能借用cc软链接到真正的C编译器。MSVC 微…...
ubuntu下qt连接mysql出现 QMYSQL driver not loaded
1、首先检查是否重新安装了MySQL的驱动,可以使用命令: sudo apt-get remove libqt5sql5-mysql sudo apt-get install libqt5sql5-mysql 2、重新安装ibmysqlclient-dev即可解决 sudo apt-get remove libmysqlclient-dev sudo apt-get install libmysq…...
html 首行缩进2字符
1. html 首行缩进2字符 1.1. 场景 在Html开发中让一段文字(富文本等)首行缩进两个文字,可能在前面加上8个“ ”,因为过去对CSS不熟悉,这种方法实现虽然比较直接,但是文字多的时候会有很多“ ”充斥在代码中…...
什么是IP?
目录 简介 IP IP协议 IP地址 发展历程 IP地址类型 公有地址 私有地址 IP地址编址方式 A类IP地址 B类IP地址 C类IP地址 D类IP地址 特殊的网址 子网 超网 无类间路由 IP地址的分配 IP地址管理 手工管理模式 DHCP分配IP地址的管理模式 通过交换机管理IP 地址…...
js拖拽交换元素位置
摘要:最近在做会议系统,9宫格小画面要支持拖拽调整顺序,需求已经实现了,简单记录下当时的逻辑处理。 /* 关于拖拽逻辑处理 start */ // 当前在拖动的下标 const curDragIndex useRef<number>(-1); /* 拖拽元素事件* onDragStart_开始* onDragend_结束 */ const handleD…...
在 C++ 中实现自定义容器的实用指南
在 C 中实现自定义容器的实用指南 在 C 编程中,容器是存储和管理数据的基本工具。标准库提供了多种容器,如 std::vector、std::list 和 std::map,但在某些情况下,开发者可能需要实现自定义容器以满足特定需求。本文将详细介绍如何…...
《深入浅出WPF》读书笔记.4名称空间详解
《深入浅出WPF》读书笔记.4名称空间详解 背景 主要讲明名称空间概念,可以理解为命名空间的引用。 xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml" 👆如x可以理解为一些列命名空间的引用。 不一一列举,只讲几个特殊的…...
电驱动总成
电驱动总成(Electric Drive Assembly)是电动汽车和混合动力汽车中关键的组成部分,主要负责将电能转化为机械能,以驱动汽车的轮胎。电驱动总成包括多个关键组件,通常可以分为以下几个主要部分: ### 主要组成…...
JavaScript class和正则
正则表达式练习 出生日期 年 月 日 ()表示一个整体 console.log(1909.match(^19\\d{2}$)); console.log(2024.match(^20(([01][0-9])|(2[0-4]))$)); //年 console.log(1909.match(^(19\\d{2})|(20(([01][0-9])|(2[0-4])))$)); // 月 console.log(12.match(^(0[1-9])|(1[0-2])…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
