【数据结构】时间复杂度(加法乘法规则、渐近时间复杂度、循环时间复杂度总结

2.2 时间复杂度

  • 什么是时间复杂度?

    评估算法时间开销

    T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))

    在实际求解中,只留表达式中最高阶的部分,丢弃其他部分。

  • 如何求解?

    • 求解步骤

      1.找到一个最深层的基本操作;

      2.分析该操作执行次数x问题规模n的关系** x = f ( n ) x=f(n) x=f(n)**;

      3.x的数量级 O ( x ) O(x) O(x)就是时间复杂度 T ( n ) T(n) T(n)

    • 求解原则

      1.顺序执行的代码只会影响常数项,可忽略。

      2.只需挑一个基本操作分析它的执行次数与n的关系即可。

      3.如果有多层嵌套循环,只需关注最深层循环了几次。

  • 规则

    • 1.加法规则

      T ( n ) = T 1 ( n ) + T 2 ( n ) = O ( f ( n ) ) + O ( g ( n ) ) = O ( m a x ( f ( n ) , g ( n ) ) ) T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n))) T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

    • 2.乘法规则

      T ( n ) = T 1 ( n ) ∗ T 2 ( n ) = O ( f ( n ) ) ∗ O ( g ( n ) ) = O ( f ( n ) ∗ g ( n ) ) T(n)=T_1(n)*T_2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)) T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)g(n))

  • 常见渐近时间复杂度

    O ( 1 ) < O ( l o g 2 n ) < O ( n ) < O ( n l o g 2 n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n ! ) < O ( n n ) O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n) O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

  • 时间复杂度分类

    最坏时间复杂度、平均时间复杂度、最好时间复杂度

    只考虑最坏时间复杂度

  • 循环时间复杂度总结

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/409039.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

yolov8添加注意力机制模块-CBAM

修改 在tasks.py&#xff08;路径&#xff1a;ultralytics-main/ultralytics-main - attention/ultralytics/nn/tasks.py&#xff09;文件中&#xff0c;引入CBAM模块。因为yolov8源码中已经包含CBAM模块&#xff0c;在conv.py文件中&#xff08;路径&#xff1a;ultralytics-…

【README 小技巧】在项目README.md 中展示github点赞数量

在项目README.md 中展示github点赞数量 [![Star History Chart](https://api.star-history.com/svg?reposwujiawei1207537021/wu-lazy-cloud-network&typeDate)](https://star-history.com/#wujiawei1207537021/wu-lazy-cloud-network&Date)效果

【微服务】mybatis typehandler使用详解

目录 一、前言 二、TypeHandler简介 2.1 什么是TypeHandler 2.1.1 TypeHandler特点 2.2 TypeHandler原理 2.3 mybatis自带的TypeHandler 三、环境准备 3.1 准备一张数据表 3.2 搭建一个springboot工程 3.2.1 基础依赖如下 3.2.2 核心配置文件 3.2.3 测试接口 四、T…

java面向对象高级

一、静态 static读作静态&#xff0c;可以用来修饰成员变量&#xff0c;也能修饰成员方法。我们先来学习static修饰成员变量。 1.1 static修饰成员变量 Java中的成员变量按照有无static修饰分为两种&#xff1a;类变量、实例变量。它们的区别如下图所示&#xff1a; 由于静态…

通过底层原理理解Java是值传递还是引用传递?

本文学习目标或者巩固的知识点 参数传递方式 值传递引用传递指针传递 彻底理解Java的值传递和引用传递 从底层的角度分析值传递会发生复制行为 Java的参数传递例子 快手的一面面试曾经问到过此类题目&#xff0c;所以记下此篇加深印象。 问&#xff1a;求下面main方法中的输…

常用状态码

状态码 用于响应中的&#xff0c;表示响应的结果如何 1、200 OK 运行成功 2、404 Not Found 访问的资源没有找到&#xff08;url的路径&#xff09; 3、403 Forbidden 请求资源没有权限访问 4、405 Method Not Allowed 你的服务器只支持GET请求&#xff0c;但是你发了个PO…

基于springboot+vue的校园社团信息管理系统(前后端分离)

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…

sizeof和strlen的对比及练习题(超详细)

创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ sizeof和strlen的对比 sizeof举例说明 sizeof计算int类型数据 &#xff08;有关于数组&#xff09;sizeof计算 strlen举例说明 strlen是C语言库函数&#xff0c;求字符串长度 函数原型&#xff1a; size_t s…

前端项目打包体积分析与优化

一、安装依赖分析工具 npm install webpack-bundle-analyz 二、修改webpack.config.js文件 1、导入上面下载的包 2、在plugins里创建实例 三、启动打包命令 npm run build 会弹出如下界面&#xff1a; 四、优化 1、通过CDN导入react-dom文件 修改webpack.config.js文件里…

掌握3个Mock工具,轻松玩转单元测试

公司要求提升单元测试的质量&#xff0c;提高代码的分支覆盖率和行覆盖率&#xff0c;安排我研究单元测试&#xff0c;指定方案分享并在开发部普及开。 单元测试中的Mock的目的 Mock的主要目的是让单元测试Write Once, Run Everywhere. 即编写一次后&#xff0c;可以在任意时…

LeetCode--代码详解 236. 二叉树的最近公共祖先

236. 二叉树的最近公共祖先 题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&am…

中国农业无人机行业市场现状分析与投资前景预测研究报告

全版价格&#xff1a;壹捌零零 报告版本&#xff1a;下单后会更新至最新版本 交货时间&#xff1a;1-2天 第一章农业无人机行业发展综述 第一节农业无人机行业定义及分类 一、农业无人机行业的定义 农业无人机是一种无人驾驶的飞行器来帮助优化农业经营&#xff0c;增加作…

找游戏 - 华为OD统一考试(C卷)

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 200分 题解&#xff1a; Java / Python / C 题目描述 小扇和小船今天又玩起来了数字游戏&#xff0c; 小船给小扇一个正整数 n&#xff08;1 ≤ n ≤ 1e9&#xff09;&#xff0c;小扇需要找到一个比 n 大的数字 m&a…

C++ //练习 8.8 修改上一题的程序,将结果追加到给定的文件末尾。对同一个输出文件,运行程序至少两次,检验数据是否得以保留。

C Primer&#xff08;第5版&#xff09; 练习 8.8 练习 8.8 修改上一题的程序&#xff0c;将结果追加到给定的文件末尾。对同一个输出文件&#xff0c;运行程序至少两次&#xff0c;检验数据是否得以保留。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工…

dolphinscheduler伪集群部署教程

文章目录 前言一、配置免密登录1. 配置root用户免密登录2. 创建用户2.1 创建dolphinscheduler用户2.2 配置dolphinscheduler用户免密登录2.3 退出dolphinscheduler用户 二、安装准备1. 安装条件2. 安装jdk3. 安装MySQL4. 安装zookeeper4.1 zookeeper单机部署4.2 启动zookeeper4…

14-ATF中对多核的支持

讨论一个系统、一个软件或ATF对多核的支持,其实就是看这个软件,在启动阶段如何区分主核、从核的? 在runtime阶段,是否能把不同核的CPU Data加以区分?是否能区分出cpuid? runtime阶段:主核和从核的区分 在启动阶段,会读取平台函数plat_is_my_cpu_primary来判单,当前是…

java 面向对象-上:类的结构之二

类的设计中&#xff0c;两个重要结构之二&#xff1a;方法 方法 描述类应该具的功能。 比如&#xff1a;Math类&#xff1a;sqrt()\random() \... Scanner类&#xff1a;nextXxx() ... Arrays类&#xff1a;sort() \ binarySearch() \ toString() \ equals() \ ... 1.举例 p…

哈希-数组中两数之和

文章目录 题目解题思路具体步骤 题目 在编程和算法学习中&#xff0c;"两数之和"问题是一个非常经典的问题&#xff0c;它不仅测试了基本的编程能力&#xff0c;还涉及到数据结构的有效使用&#xff0c;特别是哈希表。问题的描述是这样的&#xff1a; 题目&#xff…

1110. 删点成林

1110. 删点成林 关键要点 通过O(1)时间复杂度确认节点是否需要删除 Set to_deleteSet new HashSet<>(); Arrays.stream(to_delete).forEach(to_deleteSet::add); 使用深度优先搜索&#xff08;DFS&#xff09;遍历树 node.left dfs(node.left, s, ans); node.right …

Orange3数据预处理(列选择组件)数据角色及类型描述

在Orange3的文件组件中&#xff0c;datetime、categorical、numeric以及text代表不同种类的数据类型&#xff0c;具体如下&#xff1a; datetime&#xff1a;代表日期和时间类型的数据。通常用于时间序列分析、生存分析和其他需要考虑时间因素的机器学习任务中。例如&#xff0…