【时间复杂度和空间复杂度】
常见的时间复杂度
计算方法1、确定输入规模:
输入规模通常用 n 表示,例如数组长度、链表长度等。2、分析算法的执行步骤:
计算每个操作的执行次数。
确定操作的执行次数与输入规模的关系。3、忽略常数和低阶项:
在大O表示法中,常数和低阶项可以忽略,只保留最高阶项。
例如,O(3n² + 2n + 1) 简化为 O(n²)。
举例:
假设有一个算法,其执行步骤如下:arr = [1, 2, 3, 4, 5]
for i in arr: # O(n)for j in arr: # O(n)print(i, j)外层循环:执行 n 次。
内层循环:每次外层循环执行 n 次。
总执行次数:n * n = n²。
时间复杂度:O(n²)。
-
O(1):常数时间复杂度
-
不论输入规模如何,算法的执行时间是固定的。
-
示例:访问数组的某个元素。
arr = [1, 2, 3] print(arr[1]) # 时间复杂度为 O(1)
-
-
O(n):线性时间复杂度
-
算法的执行时间与输入规模成正比。
-
示例:遍历一个数组。
arr = [1, 2, 3, 4, 5] for i in arr:print(i) # 时间复杂度为 O(n)
-
-
O(n²):二次时间复杂度
-
算法的执行时间与输入规模的平方成正比。
-
示例:嵌套循环。
arr = [1, 2, 3, 4, 5] for i in arr:for j in arr:print(i, j) # 时间复杂度为 O(n²)
-
-
O(log n):对数时间复杂度
-
算法的执行时间与输入规模的对数成正比。
-
示例:二分查找。
def binary_search(arr, target):left, right = 0, len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1else:right = mid - 1return -1 # 时间复杂度为 O(log n)
-
-
O(n log n):线性对数时间复杂度
-
算法的执行时间与输入规模的对数成正比。
-
示例:快速排序、归并排序。
def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right) # 时间复杂度为 O(n log n)
-
空间复杂度
定义:空间复杂度是指算法在运行过程中消耗的内存资源量级,通常用输入规模(如数组长度、链表长度等)来表示。
表示方法:空间复杂度也用大O符号(O)表示,例如 O(1)、O(n)、O(n²) 等。
计算方法1)确定输入规模:
输入规模通常用 n 表示,例如数组长度、链表长度等。2)分析算法使用的额外内存:
计算算法中使用的额外空间(如变量、数组、递归栈等)。
确定额外空间的使用量与输入规模的关系。3)忽略常数和低阶项:
在大O表示法中,常数和低阶项可以忽略,只保留最高阶项。
例如,O(3n² + 2n + 1) 简化为 O(n²)。
假设有一个算法,其执行步骤如下:
Python复制
def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid]) # 创建左半部分数组right = merge_sort(arr[mid:]) # 创建右半部分数组return merge(left, right) # 合并两个数组
-
递归调用:每次递归调用会创建两个子数组。
-
空间复杂度:
-
每次递归调用创建的子数组占用 O(n) 的空间。
-
递归深度为 O(log n)。
-
总空间复杂度为 O(n)(递归栈空间)。
-
常见的空间复杂度
-
O(1):常数空间复杂度
-
不论输入规模如何,算法使用的额外内存是固定的。
-
示例:交换两个变量的值。
a, b = 1, 2 a, b = b, a # 空间复杂度为 O(1)
-
-
O(n):线性空间复杂度
-
算法使用的额外内存量与输入规模成正比。
-
示例:复制一个数组。
arr = [1, 2, 3, 4, 5] new_arr = arr[:] # 空间复杂度为 O(n)
-
-
O(n²):二次空间复杂度
-
算法使用的额外内存量与输入规模的平方成正比。
-
示例:创建一个二维数组。
arr = [[0] * n for _ in range(n)] # 空间复杂度为 O(n²)
-
相关文章:
【时间复杂度和空间复杂度】
常见的时间复杂度 计算方法1、确定输入规模: 输入规模通常用 n 表示,例如数组长度、链表长度等。2、分析算法的执行步骤: 计算每个操作的执行次数。 确定操作的执行次数与输入规模的关系。3、忽略常数和低阶项: 在大O表示法中&am…...
王炸 用AI+飞书 分解 一键生成 项目计划表模版
效果图: 各字段设置: 以下是一个使用 AI(DeepSeeker) 飞书多维表格分解项目待办模板的示例,你可以根据实际情况进行调整和优化: 列表中需要选择对象,且选择输出结果(记得控制字符长度…...
VisionMaster4.4 python脚本 图像处理 转换函数 爱之初体验
最近有接触过一丢丢VM4.3的模块开发. 一直有把python图像处理部分模块移植进来的打算 不过时间不够没来得及折腾.偶尔发现4.4支持py脚本 于是拿来折腾.一下午. 发现4.4支持python脚本,好开心. 首先安装VM4.4 注意一定要是4.4 打开后拖了一个模块. 但是发现import numpy imp…...
线程池的使用 + MD5加密 + 枚举类
文章目录 1、线程池的使用2、MD5算法的使用3、多用枚举类 整理下近期干活儿遇到的一些坑。 1、线程池的使用 不合理点1:jstack线程转储发现,有几万个线程,查看代码发现,线程池放在方法内部或者循环体中创建,尽管方法…...
[qt5学习笔记]Application Example示例程序源码解析
开发环境问题 vs2022下直接打开ui、ts文件失败 解决办法如下图, 设置designer独立运行。估计是嵌入运行存在些许bug。 同理,ts编辑工具linguist也存在这个问题。 qrc rc的编辑嵌入编辑都正常,但分离式更稳定可靠。 qt creator编译失败 原…...
【在时光的棋局中修行——论股市投资的诗意哲学】
在时光的棋局中修行——论股市投资的诗意哲学 引子:数字之海与星辰之约 在经纬交织的K线图里,我常看见银河倾泻的轨迹。那些跳动的数字如同繁星坠落,在午夜时分编织着财富的密码。炒股之道,是理性与诗意的交响,是数据…...
IB网络错误检查工具ibqueryerrors
ibqueryerrors 是一个用于查询 InfiniBand 网络中错误统计信息的工具。它可以帮助网络管理员识别和诊断网络问题,如丢包、重传和其他通信错误。这个工具通常是 InfiniBand 管理软件包的一部分,例如 OpenSM(Open Subnet Manager)。…...
「vue3-element-admin」Vue3 + TypeScript 项目整合 Animate.css 动画效果实战指南
🚀 作者主页: 有来技术 🔥 开源项目: youlai-mall ︱vue3-element-admin︱youlai-boot︱vue-uniapp-template 🌺 仓库主页: GitCode︱ Gitee ︱ Github 💖 欢迎点赞 👍 收藏 ⭐评论 …...
论文阅读 DOES END-TO-END AUTONOMOUS DRIVING REALLY NEED PERCEPTION TASKS?
端到端的强势来袭,好久了~~~ 简单翻译:端到端真的需要感知任务嘛? code https://github.com/PeidongLi/SSR. https://arxiv.org/pdf/2409.18341 1. 摘要 端到端自动驾驶(E2EAD)方法通常依赖于监督式感知任务来提取显…...
25年黑龙江省考报名流程详细教程
2025年黑龙江省考报名马上就要开始报名啦! 有想要参加黑龙江省考报名的同学,可以提前了解一下考试报名流程,熟悉考试报名照要求! 一、考试时间安排 报名时间:2月18日9:00至2月23日17:00 缴费时间:2月18日…...
基于SpringBoot的小区运动中心预约管理系统
作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏:…...
部署postgresql_exporter监控pgsql
部署exporter配置监控job配置告警规则 一键部署脚本 #!/bin/bash# 定义变量 PG_HOST"xx.ap-southeast-1.rds.amazonaws.com" PG_PORT"5432" PG_PASSWORD"bagayalu321" PG_USER"monitor_user" EXPORTER_VERSION"0.16.0" #…...
Mac本地部署deepseek
Ollama 运行deepseek需要本地运行工具ollama,安装路径如下 ollama官方网站 (https://ollama.com/download) 下载Mac版ollama,点击移至application下面 DeepSeek R1 14b 通过ollama安装deepseek,对应的运行指令可通过 deepseek本地部署列表…...
huggingface+下载deepseek8b lamda+本地部署 笔记
步骤倒过来 1.python hf_download.py --model unsloth/DeepSeek-R1-Distill-Llama-8B-GGUF model后加模型名(HF-Mirror中查) 【huggingface模型下载不下来?这里教你万能解决办法~huggingface小白使用指南。】 https://www.bilibili.com/video…...
中上211硕对嵌入式AI感兴趣,如何有效规划学习路径?
今天给大家分享的是一位粉丝的提问,中上211硕对嵌入式AI感兴趣,如何有效规划学习路径? 接下来把粉丝的具体提问和我的回复分享给大家,希望也能给一些类似情况的小伙伴一些启发和帮助。 同学提问: 中上211,…...
Jedis 客户端 用于java连接redis服务
<dependency><groupId>redis.clients</groupId><artifactId>jedis</artifactId...
车载诊断数据库 --- 通用性诊断数据库ODX
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 简单,单纯,喜欢独处,独来独往,不易合同频过着接地气的生活,除了生存温饱问题之外,没有什么过多的欲望,表面看起来很高冷,内心热情,如果你身…...
docker 基础命令使用(ubuntu)
docker 状态查询 docker ps docker ps -adocker --version docker info docker --help docker run --help docker ps --help ...docker 操作镜像命令 docker imagesdocker rmi 镜像id/镜像名docker 操作容器命令 docker ps docker ps -adocker run 命令 # 端口映射 -p 参数…...
IDEA集成DeepSeek
引言 随着数据量的爆炸式增长,传统搜索技术已无法满足用户对精准、高效搜索的需求。 DeepSeek作为新一代智能搜索技术,凭借其强大的语义理解与深度学习能力,正在改变搜索领域的游戏规则。 对于 Java 开发者而言,将 DeepSeek 集成…...
Unity 接入Luabn记录图解
Luban 文档及链接项目目录UnityEditor 导表工具 文档及链接 官方文档 最新版本 项目目录 接入的方法有很多,我这里随便找了一种 https://gitee.com/focus-creative-games/luban_examples.git如上图,git拉去后,只保留圈起来的2个文件夹。…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...
