什么是算法的空间复杂度和时间复杂度,分别怎么衡量。
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算法的主要步骤和特点: 主…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
