征服数据结构中的时间和空间复杂度
目录
- 时间复杂度
- 推导大O方法
- 求解时间复杂度的方法
- 普通顺序结构
- 单循环
- 双循环
- 递归
- Master定理(主定理)
- 递归树方法
- 空间复杂度
一个算法的好坏根据什么来判断呢?有两种一种是时间效率,一种是空间效率。时间效率也可称为时间复杂度,空间效率可以称为空间复杂度。时间复杂度衡量的主要是算法的运行速度而空间复杂度主要衡量的是一个算法所需要的额外空间。
时间复杂度
在进行算法分析时,语句总的执行次数 T(n) 是关于问题规模 n 的函数,进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n))。 它表示随问题规模n 的增大,算法执行时间的增长率和 f(n) 的增长率相同,称作算法的渐近时间复杂度,简称为时间复 杂度。其中f(n) 是问题规模n 的某个函数。
定义很长,个人觉得了解即可,对于O()这种体现时间复杂度的方法,我们称之为大O记法
推导大O方法
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中,只保留最高阶项。
- 如果最高阶项存在且不是1,则去除与这个项相乘的常数。
得到的结果就是大O 阶 。
求解时间复杂度的方法
时间复杂度有最坏时间复杂度,平均时间复杂度,也有最好情况的时间复杂度,但我们一般讨论的都是最坏时间按复杂度,并且如果没有特殊说明,我们也默认为算的是最坏时间复杂度。
我们去计算时间复杂度的时候,说白了也就是去数语句执行次数最多的,算出来的就是时间复杂度,不过要满足大O记法。
O(100)的时间复杂度为O(1),只有常数存在的时候,常数时间复杂度为O(1)
普通顺序结构
这种可以称作求时间复杂度最简单的。
public static void main(String[] args) {System.out.println("你好!");}//执行了常数次,时间复杂度为O(1)
单循环
我建议大家做这种的时候要多动手,而不是光靠脑子想。尤其我们刚开始接触数据结构的时候。
public void func(int n) {int i = 1;while (i <= n) {i = i * 2;}}

这里给大家留一个题,自己动手试试,看是否真懂了呢?
// 计算func4的时间复杂度?
void func4(int N) {
int count = 0;
for (int k = 0; k < n; k++) {
count++;
}
System.out.println(count);
}
双循环
这种分为两种,一种是内外两层互不影响,一种是外层会影响内层。
- 两层互不影响的时候

我们一般把log₂n简写成logn - 外层会对内层产生影响的时候
public void func2(int n) {int m = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= (2 * i); j++) {m++;}}}

希望大家能掌握这种方法,这样对于多层循环也就不害怕了,道理都一样
递归
前段时间看到一个求递归算法时间复杂度的视频,我觉得很容易让人理解,希望也能帮助到你们。
Master定理(主定理)
* 我们比较下面这两个哪个时间复杂度大就用哪个

一、规则一
如果左半部大,那么我们最后直接取左半部分作为结果

二、规则二
如果上面两个算出结果相等,我们需要取左半部分结果再乘上logn,两个组合起来才为最后结果

三、规则三
当比较两个,如果右边大,我们需要再判断下面图片这个式子

如果计算后均满足这两个条件,最后结果就是右边的那个结果。
递归树方法

我们拿第一个举例。

我们画出了递归树,这种求解复杂度方法是:叶子数 + 层数 * f(n)
对于上面这些方法,核心还是要根据代码能推出正确的式子。T(n)=T(n-1)+ 其余操作的时间复杂度,这个式子含义就是求时间复杂度的时候等于前n-1的时间复杂度加上另外一些其他的操作所需要用到的时间复杂度。
时间复杂度大小排序:O(1)<0(logn)<0(n)<0(nlogn)<0(n²)<0(n³)<0(2”)<0(n!)<O(n”)
空间复杂度
算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n)=0(f(n)), 其 中 ,n 为问题的规模,f(n) 为语句关于 n 所占存储空间的函数。空间复杂度的求解也符合大O记法。
穿插个题外话,现在估计还有好多人弄不清KB,GB,MB的大小关系,希望大家能记住,因为不知道啥时候就会用到。
1GB=1024MB 1MB=1024KB 1KB=1024字节
- 我们在计算空间复杂度的时候,计算的是变量的个数而不是占用了多少空间。
- 函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
空间复杂度的计算,这我就不细说了,相信大家都有相关的教材,这部分可以参考教材来学习怎么计算
相关文章:
征服数据结构中的时间和空间复杂度
目录 时间复杂度推导大O方法求解时间复杂度的方法普通顺序结构单循环双循环递归Master定理(主定理)递归树方法 空间复杂度 一个算法的好坏根据什么来判断呢?有两种一种是时间效率,一种是空间效率。时间效率也可称为时间复杂度&…...
springboot Security vue
在使用Spring Boot Security与Vue.js构建前后端分离的应用时,你需要处理几个关键的技术点,包括认证(Authentication)和授权(Authorization),以及如何处理跨域请求(CORS)、…...
13. 计算机网络HTTPS协议(一)
1. 前言 在上一章节中我们介绍了 HTTP 协议相关的面试题目,作为 HTTP 协议的扩展,HTTPS 协议也经常被面试官提起。 因为对于大部分的前端、后端开发者,都接触不到 HTTPS 协议的开发场景,因为我们往往只关注请求路径后缀,例如关注 URL: /get/username,而非路径全称 htt…...
Bean的作用域和生命周期
Bean的作用域 我们先来看下面这段代码 首先是一个Dog类 (此处使用lombok来完成setter、getter、toString方法) Setter Getter public class Dog {private String name;} 然后在DogBeanConfig类里面写一个返回Dog的方法,并将这个方法的返…...
【Qt】QMainWindow之菜单栏
目录 一.菜单栏 1.概念 2.组成 二.代码创建菜单栏 1.创建菜单栏 2.在菜单栏中添加菜单 3.在菜单中添加菜单项 三.图形化创建菜单栏 1.在打开Qt自带的ui文件界面后,得到以下界面 2.双击点击界面中(在这里输入),在菜单栏中进行…...
uni-app封装组件实现下方滑动弹出模态框
子组件 <template><div class"bottom-modal" :class"{show: showModal}"><div class"modal-content" :class"{show: showModal}"><!-- 内容区域 --><slot></slot></div></div></…...
MATLAB(15)分类模型
一、前言 在MATLAB中,实现不同类型的聚类(如K-means聚类、层次聚类、模糊聚类)和分类(如神经网络分类)需要用到不同的函数和工具箱。下面我将为每种方法提供一个基本的示例代码。 二、实现 1. K-means聚类 % 假设X是…...
非虚拟机安装Centos7连接wifi并开机自动联网
一:确认网卡名称 ip addr 无线网卡是以 w 开头,确定是wlp4s0 ,有的是 wlp5s0 二:配置网络 wpa_supplicant -B -i wlp4s0 -c <(wpa_passphrase "网络的名字" “网络的密码“) 设置自动分配IP dhclient wlp4s0 三&…...
怎么选择的开放式耳机好用?2024超值耳机分享!
耳机在当前数字化时代已成为我们生活、娱乐乃至工作中的重要部分。随着市场需求的增长,消费者对耳机的期望也在提高,他们不仅追求音质的卓越,还关注佩戴的舒适度和外观设计。虽然传统的入耳式和半入耳式耳机在音质上往往能够满足人们…...
Web 框架
Web 框架 Web服务器Web服务器的主要功能常见的Web服务器软件包 Web 框架常用 Python Web 框架选择Python Web框架的考虑因素 WSGIWSGI的主要特点WSGI的工作原理常见的WSGI服务器和框架: 静态资源定义与特点静态资源的类型静态资源的管理与优化 动态资源定义与特点动…...
嗖嗖移动业务大厅(JDBC)
一、项目介绍 1、项目背景: 该项目旨在模拟真实的移动业务大厅,。用户可以注册新卡、查询账单、管理套餐、充值话费、打印消费记录等功能。同时,项目还模拟了用户使用场景,如通话、上网、发短信等,并根据套餐规则进行相应的扣费…...
大学生编程入门指南:如何从零开始?
人不走空 🌈个人主页:人不走空 💖系列专栏:算法专题 ⏰诗词歌赋:斯是陋室,惟吾德馨 目录 编程语言选择 📚 1. Python 2. JavaScript 3. Java 4. C/C 如何选择适合自己的编程语言&a…...
如何基于欧拉系统完成数据库的安装
一、安装 当我们直接进行安装软件包时,会提示有冲突,此时,我们应该这样来解决 使用rpm命令 [rootlocalhost yum.repos.d]# rpm -qa | grep selinux使用 rpm命令卸载以下两个软件包 [rootlocalhost yum.repos.d]# rpm -e selinux-policy-3…...
防御笔记第九天(持续更新)
注意:攻击可能只是一个点,而防御需要全方面进行。 1.IAE引擎 2.DPI DPI ----深度包检测 --- 针对完整的数据包,进行内容的识别和检测 3.基于特征字的检测技术 4,基于应用网关的检测技术 基于应用网关的检测技术 --- 有些应用控…...
html+css+js前端作业和平精英6个页面页面带js
htmlcssjs前端作业和平精英6个页面页面带js 下载地址 https://download.csdn.net/download/qq_42431718/89595600 目录1 目录2 项目视频 htmlcssjs前端作业和平精英6个页面带js 页面1 页面2 页面3 页面4 页面5 页面6...
详解基于百炼平台及函数计算快速上线网页AI助手
引言 在当今这个信息爆炸的时代,用户对于在线服务的需求越来越趋向于即时性和个性化。无论是寻找产品信息、解决问题还是寻求建议,人们都期望能够获得即时反馈。这对企业来说既是挑战也是机遇——如何在海量信息中脱颖而出,提供高效且贴心的…...
【TVM 教程】在 CUDA 上部署量化模型
更多 TVM 中文文档可访问 →Apache TVM 是一个端到端的深度学习编译框架,适用于 CPU、GPU 和各种机器学习加速芯片。 | Apache TVM 中文站 作者:Wuwei Lin 本文介绍如何用 TVM 自动量化(TVM 的一种量化方式)。有关 TVM 中量化的…...
使用 continue 自定义 AI 编程环境
一直在使用github 的 copilot 来编程,确实好用,对编码效率有很大提升。 但是站在公司角度,因为它只能对接公网(有代码安全问题)。另外,它的扩展能力也不强,无法适配公司特定领域的知识库&#x…...
谷粒商城实战笔记-118-全文检索-ElasticSearch-进阶-aggregations聚合分析
文章目录 一,基本概念主要聚合类型 二,实战1,搜索 address 中包含 mill 的所有人的年龄分布以及平均年龄,但不显示这些人的详情2,按照年龄聚合,并且请求每个年龄的平均薪资 Elasticsearch 的聚合࿰…...
ansible,laas,pass,sass
ansible是新出现的自动化运维工具,基于Python开发,集合了众多运维工具(puppet、chef、func、fabric)的优点,实现了批量系统配置、批量程序部署、批量运行命令等功能。ansible是基于 paramiko 开发的,并且基于模块化工作…...
人脸检测开源生态新成员:cv_resnet101_face-detection_cvpr22papermogface ModelScope集成详解
人脸检测开源生态新成员:cv_resnet101_face-detection_cvpr22papermogface ModelScope集成详解 1. 项目概述 今天要介绍的是一个特别实用的人脸检测工具——基于MogFace模型开发的本地高精度人脸检测系统。这个工具解决了PyTorch新版本加载旧模型的兼容性问题&…...
路径跟踪惩罚
基于动力学模型MPC的加入规划层的轨迹跟踪避障控制(优化过的,效果比书本的好)半夜调试控制器的时候,突然发现传统轨迹跟踪像极了直男开车——死盯目标点不管周围环境。这周给移动机器人怼了个混合架构,把全局规划直接喂…...
中国空间智能,梦想照进现实
2026年初,AI教母李飞飞的AI公司World Labs再次获得一笔10亿美元的投资,投资名单除了传统投资机构外,还不乏英伟达、Autodesk等行业巨头,这清晰地传递出市场信号:继AI大语言模型之后,空间智能已成为AI的下一…...
计算机毕业设计springboot校园外卖系统 基于Spring Boot的高校餐饮配送服务平台 Spring Boot框架下的校园在线订餐与配送管理系统
计算机毕业设计springboot校园外卖系统n322b9 (配套有源码 程序 mysql数据库 论文) 本套源码可以在文本联xi,先看具体系统功能演示视频领取,可分享源码参考。随着互联网技术的日益成熟和普及,网络已经深度融入人们的日常生活&…...
基于.NET 11 与C# 14的高性能安全客户端应用开发
基于.NET 11 与C# 14的高性能安全客户端应用开发 前言 在客户端应用开发领域,性能与安全始终是关键指标。随着.NET 11 和 C# 14 的推出,开发者拥有了更强大的工具来构建高性能且安全可靠的客户端应用。这些新技术不仅提升了应用的运行效率,还…...
sklearn分类指标实战:如何用precision_recall_curve优化你的模型效果
sklearn分类指标实战:如何用precision_recall_curve优化模型效果 在机器学习项目中,分类模型的评估往往比训练过程更考验数据科学家的专业素养。当你的模型在测试集上达到95%的准确率时,是否就意味着可以高枕无忧?现实情况往往复杂…...
从热电偶到串口显示:用STM32F103C8T6+MAX6675搭建简易温度监控系统
从零搭建热电偶温度监控系统:STM32F103C8T6与MAX6675实战指南 在工业测量和创客项目中,温度监控是最基础却至关重要的环节。想象一下,当你需要精确控制3D打印机的热床温度、监测烘焙设备的加热曲线,或是记录温室大棚的环境变化时&…...
避开版本坑!用DINOv2和MMSegmentation在PASCAL VOC 2012上跑通语义分割(附完整环境配置)
避开版本坑!用DINOv2和MMSegmentation在PASCAL VOC 2012上跑通语义分割(附完整环境配置) 语义分割作为计算机视觉领域的核心任务之一,其技术演进始终与深度学习框架的生态紧密相连。当Meta开源的DINOv2遇上OpenMMLab的MMSegmentat…...
Windows系统焕新优化:Win11Debloat全方位性能提升指南
Windows系统焕新优化:Win11Debloat全方位性能提升指南 【免费下载链接】Win11Debloat 一个简单的PowerShell脚本,用于从Windows中移除预装的无用软件,禁用遥测,从Windows搜索中移除Bing,以及执行各种其他更改以简化和改…...
C#搞CV别再跪了!OpenCVSharp的SIFT/SURF实现:我熬3夜踩5个坑,吐血整理保姆级代码
🌪️ 一、先泼冰水:SIFT/SURF的“专利坟场”,别往里跳!(血泪预警) ⚠️ 重点敲黑板: SURF已凉透:OpenCV 4.5.0 彻底移除!别再搜“怎么用SURF”,纯属浪费生命&…...
