当前位置: 首页 > news >正文

征服数据结构中的时间和空间复杂度

目录

  • 时间复杂度
    • 推导大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取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中,只保留最高阶项。
  3. 如果最高阶项存在且不是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);
}

双循环

这种分为两种,一种是内外两层互不影响,一种是外层会影响内层。

  1. 两层互不影响的时候
    在这里插入图片描述
    我们一般把log₂n简写成logn
  2. 外层会对内层产生影响的时候
    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定理&#xff08;主定理&#xff09;递归树方法 空间复杂度 一个算法的好坏根据什么来判断呢&#xff1f;有两种一种是时间效率&#xff0c;一种是空间效率。时间效率也可称为时间复杂度&…...

springboot Security vue

在使用Spring Boot Security与Vue.js构建前后端分离的应用时&#xff0c;你需要处理几个关键的技术点&#xff0c;包括认证&#xff08;Authentication&#xff09;和授权&#xff08;Authorization&#xff09;&#xff0c;以及如何处理跨域请求&#xff08;CORS&#xff09;、…...

13. 计算机网络HTTPS协议(一)

1. 前言 在上一章节中我们介绍了 HTTP 协议相关的面试题目,作为 HTTP 协议的扩展,HTTPS 协议也经常被面试官提起。 因为对于大部分的前端、后端开发者,都接触不到 HTTPS 协议的开发场景,因为我们往往只关注请求路径后缀,例如关注 URL: /get/username,而非路径全称 htt…...

Bean的作用域和生命周期

Bean的作用域 我们先来看下面这段代码 首先是一个Dog类 &#xff08;此处使用lombok来完成setter、getter、toString方法&#xff09; Setter Getter public class Dog {private String name;} 然后在DogBeanConfig类里面写一个返回Dog的方法&#xff0c;并将这个方法的返…...

【Qt】QMainWindow之菜单栏

目录 一.菜单栏 1.概念 2.组成 二.代码创建菜单栏 1.创建菜单栏 2.在菜单栏中添加菜单 3.在菜单中添加菜单项 三.图形化创建菜单栏 1.在打开Qt自带的ui文件界面后&#xff0c;得到以下界面 2.双击点击界面中&#xff08;在这里输入&#xff09;&#xff0c;在菜单栏中进行…...

uni-app封装组件实现下方滑动弹出模态框

子组件 <template><div class"bottom-modal" :class"{show: showModal}"><div class"modal-content" :class"{show: showModal}"><!-- 内容区域 --><slot></slot></div></div></…...

MATLAB(15)分类模型

一、前言 在MATLAB中&#xff0c;实现不同类型的聚类&#xff08;如K-means聚类、层次聚类、模糊聚类&#xff09;和分类&#xff08;如神经网络分类&#xff09;需要用到不同的函数和工具箱。下面我将为每种方法提供一个基本的示例代码。 二、实现 1. K-means聚类 % 假设X是…...

非虚拟机安装Centos7连接wifi并开机自动联网

一&#xff1a;确认网卡名称 ip addr 无线网卡是以 w 开头&#xff0c;确定是wlp4s0 &#xff0c;有的是 wlp5s0 二&#xff1a;配置网络 wpa_supplicant -B -i wlp4s0 -c <(wpa_passphrase "网络的名字" “网络的密码“) 设置自动分配IP dhclient wlp4s0 三&…...

怎么选择的开放式耳机好用?2024超值耳机分享!

耳机在当前数字化时代已成为我们生活、娱乐乃至工作中的重要部分。随着市场需求的增长&#xff0c;消费者对耳机的期望也在提高&#xff0c;他们不仅追求音质的卓越&#xff0c;还关注佩戴的舒适度和外观设计。虽然传统的入耳式和半入耳式耳机在音质上往往能够满足人们&#xf…...

Web 框架

Web 框架 Web服务器Web服务器的主要功能常见的Web服务器软件包 Web 框架常用 Python Web 框架选择Python Web框架的考虑因素 WSGIWSGI的主要特点WSGI的工作原理常见的WSGI服务器和框架&#xff1a; 静态资源定义与特点静态资源的类型静态资源的管理与优化 动态资源定义与特点动…...

嗖嗖移动业务大厅(JDBC)

一、项目介绍 1、项目背景: 该项目旨在模拟真实的移动业务大厅&#xff0c;。用户可以注册新卡、查询账单、管理套餐、充值话费、打印消费记录等功能。同时&#xff0c;项目还模拟了用户使用场景&#xff0c;如通话、上网、发短信等&#xff0c;并根据套餐规则进行相应的扣费…...

大学生编程入门指南:如何从零开始?

人不走空 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌赋&#xff1a;斯是陋室&#xff0c;惟吾德馨 目录 编程语言选择 &#x1f4da; 1. Python 2. JavaScript 3. Java 4. C/C 如何选择适合自己的编程语言&a…...

如何基于欧拉系统完成数据库的安装

一、安装 当我们直接进行安装软件包时&#xff0c;会提示有冲突&#xff0c;此时&#xff0c;我们应该这样来解决 使用rpm命令 [rootlocalhost yum.repos.d]# rpm -qa | grep selinux使用 rpm命令卸载以下两个软件包 [rootlocalhost yum.repos.d]# rpm -e selinux-policy-3…...

防御笔记第九天(持续更新)

注意&#xff1a;攻击可能只是一个点&#xff0c;而防御需要全方面进行。 1.IAE引擎 2.DPI DPI ----深度包检测 --- 针对完整的数据包&#xff0c;进行内容的识别和检测 3.基于特征字的检测技术 4&#xff0c;基于应用网关的检测技术 基于应用网关的检测技术 --- 有些应用控…...

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助手

引言 在当今这个信息爆炸的时代&#xff0c;用户对于在线服务的需求越来越趋向于即时性和个性化。无论是寻找产品信息、解决问题还是寻求建议&#xff0c;人们都期望能够获得即时反馈。这对企业来说既是挑战也是机遇——如何在海量信息中脱颖而出&#xff0c;提供高效且贴心的…...

【TVM 教程】在 CUDA 上部署量化模型

更多 TVM 中文文档可访问 →Apache TVM 是一个端到端的深度学习编译框架&#xff0c;适用于 CPU、GPU 和各种机器学习加速芯片。 | Apache TVM 中文站 作者&#xff1a;Wuwei Lin 本文介绍如何用 TVM 自动量化&#xff08;TVM 的一种量化方式&#xff09;。有关 TVM 中量化的…...

使用 continue 自定义 AI 编程环境

一直在使用github 的 copilot 来编程&#xff0c;确实好用&#xff0c;对编码效率有很大提升。 但是站在公司角度&#xff0c;因为它只能对接公网&#xff08;有代码安全问题&#xff09;。另外&#xff0c;它的扩展能力也不强&#xff0c;无法适配公司特定领域的知识库&#x…...

谷粒商城实战笔记-118-全文检索-ElasticSearch-进阶-aggregations聚合分析

文章目录 一&#xff0c;基本概念主要聚合类型 二&#xff0c;实战1&#xff0c;搜索 address 中包含 mill 的所有人的年龄分布以及平均年龄&#xff0c;但不显示这些人的详情2&#xff0c;按照年龄聚合&#xff0c;并且请求每个年龄的平均薪资 Elasticsearch 的聚合&#xff0…...

ansible,laas,pass,sass

ansible是新出现的自动化运维工具&#xff0c;基于Python开发&#xff0c;集合了众多运维工具&#xff08;puppet、chef、func、fabric&#xff09;的优点&#xff0c;实现了批量系统配置、批量程序部署、批量运行命令等功能。ansible是基于 paramiko 开发的,并且基于模块化工作…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...

深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙

WebGL&#xff1a;在浏览器中解锁3D世界的魔法钥匙 引言&#xff1a;网页的边界正在消失 在数字化浪潮的推动下&#xff0c;网页早已不再是静态信息的展示窗口。如今&#xff0c;我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室&#xff0c;甚至沉浸式的V…...