当前位置: 首页 > 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 开发的,并且基于模块化工作…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...