什么是时间复杂度、什么是空间复杂度？-北京尧图网络

在 Java 算法以及所有计算机科学领域中时间复杂度和空间复杂度是衡量算法效率的两个核心指标。它们通常使用大 O 表示法Big O Notation来描述。简单来说它们衡量的是当数据规模通常用 nn 表示增大时算法的执行时间或内存消耗是如何变化的。1. 时间复杂度 (Time Complexity)定义时间复杂度并不是指代码运行的“绝对时间”比如 2 秒或 5 毫秒而是指算法中基本操作的执行次数与数据规模 nn 之间的增长关系。在 Java 中如何看看循环单层循环通常是 O(n)O(n) 嵌套循环通常是 O(n2)O(n2) 。看递归需要结合递归树的深度和每层的操作次数。看 Java APIArrayList.get(i)是 O(1)O(1) 而ArrayList.remove(0)是 O(n)O(n) 因为后续元素都要往前挪。常见的时间复杂度从快到慢O(1)O(1)常数时间无论数据多少执行时间不变。例如数组按索引取值。O(log⁡n)O(logn)对数时间每次操作数据量减半。例如二分查找。O(n)O(n)线性时间执行次数与数据量成正比。例如遍历一次数组。O(nlog⁡n)O(nlogn)线性对数时间高效排序算法的典型复杂度。例如Java 的Arrays.sort()双轴快排/归并。O(n2)O(n2)平方时间双重嵌套循环。例如冒泡排序、简单的两数之和暴力解法。2. 空间复杂度 (Space Complexity)定义空间复杂度是指算法在运行过程中临时占用存储空间的大小与数据规模 nn 之间的增长关系。⚠️ Java 中的关键注意点在 Java 中空间复杂度主要关注额外空间Auxiliary Space即除了输入数据本身占用的内存外算法还需要多少额外内存。常见场景O(1)O(1)常数空间只用了几个固定的变量没有创建新的集合或大数组。// 无论 n 多大只用了一个 sum 变量 int sum 0; for(int i0; in; i) sum i;O(n)O(n)线性空间创建了一个与输入规模相关的新数组或集合。// 创建了一个长度为 n 的新数组 int[] copy new int[n];O(n)O(n)递归栈空间Java 的递归调用会占用栈内存。如果递归深度为 nn 空间复杂度就是 O(n)O(n) 。// 递归 n 次栈帧占用 O(n) 空间 void recursion(int n) { if(n 0) return; recursion(n-1); }3. 一个直观的 Java 例子假设我们要计算 12...n12...n 方案 A循环long sum 0; // O(1) 空间 for (int i 1; i n; i) { // 循环 n 次 sum i; // 基本操作 }时间复杂度O(n)O(n)空间复杂度O(1)O(1)方案 B数学公式return n * (n 1) / 2; // 只做一次乘法和除法时间复杂度O(1)O(1)空间复杂度O(1)O(1)总结指标关注点核心问题时间复杂度CPU 执行次数数据量翻倍代码要多跑多少倍空间复杂度内存额外占用数据量翻倍需要多申请多少内存在实际开发中我们通常追求时间换空间或空间换时间的平衡。例如用HashMap缓存结果增加 O(n)O(n) 空间来将查找时间从 O(n)O(n) 降到 O(1)O(1) 这就是典型的空间换时间。

什么是时间复杂度、什么是空间复杂度？

相关推荐

06-高级模式与实战项目——10. 组件测试 - React Testing Library

华为加速商业市场AI落地：要让鲲鹏昇腾算力像用水电一样便利

HarmonyKit | 鸿蒙新特性：cryptoFramework 异步加密哈希计算实战

更多资讯

附录 A · 工具速查表

PDO属性设置全解析：高效数据库操作秘诀

GMSK调制与基于Laurent分解的GMSK解调FPGA实现，第一篇（GMSK调制篇）

JAVA——抽象类、内部类和接口

二叉树的学习

DouK-Downloader 实操指南：从 Cookie 配置到 Docker 部署的抖音/TikTok 批量下载与数据采集

今日更新

多智能体协作系统架构设计与实践优化

大模型系统性入门实战指南：从原理到部署微调的全链路路线

鸿蒙文件系统沙箱机制解析与开发实践

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？