什么是算法的空间复杂度和时间复杂度,分别怎么衡量。
1. 时间复杂度
时间复杂度衡量的是算法运行时间与输入规模之间的关系。它通常用大O记号(Big O Notation)表示,例如 O(1)、O(n)、O(n2) 等。
衡量方法:
-
常数时间复杂度 O(1):无论输入规模如何,算法的执行时间是固定的。
-
线性时间复杂度 O(n):算法的执行时间与输入规模成正比。
-
平方时间复杂度 O(n2):算法的执行时间与输入规模的平方成正比。
-
对数时间复杂度 O(logn):算法的执行时间与输入规模的对数成正比。
2. 空间复杂度
空间复杂度衡量的是算法运行过程中额外占用的内存空间与输入规模之间的关系。它也用大O记号表示。
衡量方法:
-
常数空间复杂度 O(1):算法运行过程中只占用固定数量的额外空间。
-
线性空间复杂度 O(n):算法运行过程中占用的额外空间与输入规模成正比。
-
平方空间复杂度 O(n2):算法运行过程中占用的额外空间与输入规模的平方成正比。
示例:C语言程序
示例1:线性搜索(时间复杂度 O(n),空间复杂度 O(1))
#include <stdio.h>int linearSearch(int arr[], int n, int target) {for (int i = 0; i < n; i++) { // 遍历数组,时间复杂度 O(n)if (arr[i] == target) {return i; // 找到目标值,返回索引}}return -1; // 未找到目标值,返回 -1
}int main() {int arr[] = {10, 20, 30, 40, 50};int n = sizeof(arr) / sizeof(arr[0]);int target = 30;int result = linearSearch(arr, n, target);if (result != -1) {printf("Element found at index %d\n", result);} else {printf("Element not found\n");}return 0;
}
分析:
-
时间复杂度:O(n),因为算法需要遍历整个数组。
-
空间复杂度:O(1),因为算法只使用了常量级的额外空间(变量
i和result)。
示例2:冒泡排序(时间复杂度 O(n2),空间复杂度 O(1))
#include <stdio.h>void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) { // 外层循环 n-1 次for (int j = 0; j < n - i - 1; j++) { // 内层循环 n-i-1 次if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp; // 交换相邻元素}}}
}void printArray(int arr[], int n) {for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);printf("Original array: ");printArray(arr, n);bubbleSort(arr, n);printf("Sorted array: ");printArray(arr, n);return 0;
}
分析:
-
时间复杂度:O(n2),因为算法包含两层嵌套循环。
-
空间复杂度:O(1),因为算法只使用了常量级的额外空间(变量
i、j和temp)。
示例3:递归实现的斐波那契数列(时间复杂度 O(2n),空间复杂度 O(n))
#include <stdio.h>int fibonacci(int n) {if (n <= 1) {return n; // 基本情况}return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用
}int main() {int n = 10;printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));return 0;
}
分析:
-
时间复杂度:O(2n),因为递归树的深度为 n,每个节点都有两个分支。
-
空间复杂度:O(n),因为递归调用栈的最大深度为 n。
总结
-
时间复杂度:衡量算法的运行时间,通常用大O记号表示。
-
空间复杂度:衡量算法运行过程中占用的额外内存空间,也用大O记号表示。
-
在实际开发中,时间和空间复杂度需要综合考虑,以选择最适合问题的算法。
相关文章:
什么是算法的空间复杂度和时间复杂度,分别怎么衡量。
1. 时间复杂度 时间复杂度衡量的是算法运行时间与输入规模之间的关系。它通常用大O记号(Big O Notation)表示,例如 O(1)、O(n)、O(n2) 等。 衡量方法: 常数时间复杂度 O(1):无论输入规模如何,算法的执行时…...
VMware Workstation 17.0 Pro创建虚拟机并安装Ubuntu22.04与ubuntu20.04(双版本同时存在)《包含小问题总结》
目录 一、创建虚拟机 二、下载安装22.04 三、一些配置问题总结(小屏,网络,复制贴贴等) 1、网络问题 2、sudo apt install net-tools出现无法定为软件包 3、小屏与ubuntu虚拟机与windows系统之间复制粘贴 4、安装终端:Termi…...
Windows 10 ARM工控主板CAN总线实时性能测试
在常规的Windows系统中支持CAN总线应用,需要外接CAN总线适配器,通常为USB转CAN模块或PCI接口CAN卡。实时性本身是CAN总线的显著特性之一,但由于Windows并非实时操作系统,应用程序容易受到系统CPU负载影响,导致调度周期…...
如何在不依赖函数调用功能的情况下结合工具与大型语言模型
当大型语言模型(LLM)原生不支持函数调用功能时,如何实现智能工具调度?本文通过自然语言解析结构化输出控制的方法来实现。 GitHub代码地址 核心实现步骤 定义工具函数 使用tool装饰器声明可调用工具: from langcha…...
【Linux AnolisOS】关于Docker的一系列问题。尤其是拉取东西时的网络问题,镜像源问题。
AnolisOS 8中使用Docker部署(全)_anolis安装docker-CSDN博客 从在虚拟机安装龙蜥到安装docker上面这篇文章写的很清晰了,我重点讲述我解决文章里面问题一些的方法。 问题1: docker: Get https://registry-1.docker.io/v2/: net/h…...
【Elasticsearch】Mapping概述
以下是Elasticsearch中提到的关于Mapping的各模块概述: --- 1.Dynamic mapping(动态映射) 动态映射是指Elasticsearch在索引文档时,自动检测字段类型并创建字段映射的过程。当你首次索引一个文档时,Elasticsearch会根…...
GPT-4o悄然升级:能力与个性双突破,AI竞技场再掀波澜
在大模型竞技场中,GPT-4o悄悄发布了全新版本,凭借其卓越的多项能力,迅速超越了DeepSeek-R1,成功登上并列第一的位置。这次更新不仅在数学(第6名)上有所突破,还在创意写作、编程、指令遵循、长文…...
如何选择合适的超参数来训练Bert和TextCNN模型?
选择合适的超参数来训练Bert和TextCNN模型是一个复杂但关键的过程,它会显著影响模型的性能。以下是一些常见的超参数以及选择它们的方法: 1. 与数据处理相关的超参数 最大序列长度(max_length) 含义:指输入到Bert模…...
C# SpinLock 类 使用详解
总目录 前言 SpinLock 是 C# 中一种轻量级的自旋锁,属于 System.Threading 命名空间,专为极短时间锁竞争的高性能场景设计。它通过忙等待(自旋)而非阻塞线程来减少上下文切换开销,适用于锁持有时间极短(如…...
【linux】在 Linux 上部署 DeepSeek-r1:32/70b:解决下载中断问题
【linux】在 Linux 上部署 DeepSeek-r1:32/70b:解决下载中断问题 【承接商业广告,如需商业合作请+v17740568442】 文章目录 【linux】在 Linux 上部署 DeepSeek-r1:32/70b:解决下载中断问题问题描述:解决方法方法一:手动中断并重启下载方法二:使用 Bash 脚本自动化下载在…...
机器学习所需要的数学知识【01】
总览 导数 行列式 偏导数 概理论 凸优化-梯度下降 kkt条件...
4.【线性代数】——矩阵的LU分解
四 矩阵的LU分解 1. AB的逆矩阵2. 转置矩阵3. ALU3.1 2x2矩阵3.2 3x3矩阵3.3 nxn的矩阵分解的次数? 1. AB的逆矩阵 { ( A B ) ( B − 1 A − 1 ) I ( B − 1 A − 1 ) ( A B ) I ⇒ ( A B ) − 1 B − 1 A − 1 \begin{cases} (AB)(B^{-1}A^{-1}) I\\ (B^{-1}A^…...
【清晰教程】本地部署DeepSeek-r1模型
【清晰教程】通过Docker为本地DeepSeek-r1部署WebUI界面-CSDN博客 目录 Ollama 安装Ollama DeepSeek-r1模型 安装DeepSeek-r1模型 Ollama Ollama 是一个开源工具,专注于简化大型语言模型(LLMs)的本地部署和管理。它允许用户在本地计算机…...
Spring Cloud工程搭建
目录 工程搭建 搭建父子工程 创建父工程 Spring Cloud版本 创建子项目-订单服务 声明项⽬依赖 和 项⽬构建插件 创建子项目-商品服务 声明项⽬依赖 和 项⽬构建插件 工程搭建 因为拆分成了微服务,所以要拆分出多个项目,但是IDEA只能一个窗口有一…...
使用Redis实现分布式锁,基于原本单体系统进行业务改造
一、单体系统下,使用锁机制实现秒杀功能,并限制一人一单功能 1.流程图: 2.代码实现: Service public class VoucherOrderServiceImpl extends ServiceImpl<VoucherOrderMapper, VoucherOrder> implements IVoucherOrderSe…...
【MediaTek】 T750 openwrt-23.05编 cannot find dependency libexpat for libmesode
MediaTek T750 T750 采用先进的 7nm 制程,高度集成 5G 调制解调器和四核 Arm CPU,提供较强的功能和配置,设备制造商得以打造精巧的高性能 CPE 产品,如固定无线接入(FWA)路由器和移动热点。 MediaTek T750 平台是一款综合的芯片组,集成了 5G SoC MT6890、12nm 制程…...
CHARMM-GUI EnzyDocker: 一个基于网络的用于酶中多个反应状态的蛋白质 - 配体对接的计算平台
❝ "CHARMM-GUI EnzyDocker for Protein−Ligand Docking of Multiple Reactive States along a Reaction Coordinate in Enzymes"介绍了 CHARMM-GUI EnzyDocker,这是一个基于网络的计算平台,旨在简化和加速 EnzyDock 对接模拟的设置过程&…...
c# 2025/2/17 周一
16. 《表达式,语句详解4》 20 未完。。 表达式,语句详解_4_哔哩哔哩_bilibili...
vite【详解】常用配置 vite.config.js / vite.config.ts
官网 https://cn.vitejs.dev/guide/ vite 常用配置 Vite 配置文件通常是 vite.config.js (使用 CommonJS 语法)或者 vite.config.ts(使用 TypeScript 语法),默认内容为 import { defineConfig } from vite import vue…...
最新智能优化算法: 阿尔法进化(Alpha Evolution,AE)算法求解23个经典函数测试集,MATLAB代码
一、阿尔法进化算法 阿尔法进化(Alpha Evolution,AE)算法是2024年提出的一种新型进化算法,其核心在于通过自适应基向量和随机步长的设计来更新解,从而提高算法的性能。以下是AE算法的主要步骤和特点: 主…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
