数据结构 - 语句的频度和时间复杂度

一、语句频度:

  • 算法的运行时间 = Σ每条语句的执行次数X该语句执行一次所需的时间
  • 每条语句的执行次数,也称为:语句的频度
  • 结合上面两点,可知:算法的运行时间 = Σ每条语句的频度X该语句执行一次所需的时间

二、语句执行一次所需的时间

  • 每条语句执行一次所需的时间,是由机器本身的软硬件环境决定的,与算法无关。
  • 因此,我们可假设执行每条语句所需时间为单位时间
  • 由上可知,对算法运行时间的讨论,可转化为讨论:频度之和

三、渐进时间复杂度(简称:时间复杂度)

1、例如对于求解矩阵相乘问题,算法耗费时间为:
T(n)=2n³+3n²+2n+1,T(n)即为语句频度
2、那么对于上面提到的T(n),T(n)与n³是同阶或同数量级,那么T(n)的时间复杂度为:
T(n)=O(n³)
3、算法时间复杂度:只需要看算法中执行次数最多的那条语句(也称为,该算法中的基本语句),看它执行了多少次即可。
在这里插入图片描述
4、当n很大时,指数时间算法和多项式时间算法在所需时间上非常悬殊。
在这里插入图片描述
时间复杂度T(n)按数量级递增顺序为:
在这里插入图片描述

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

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

相关文章

element时间选择器el-date-picter使用disabledDate指定禁用的日期

需要的效果 <el-date-pickerclass"selectstyle"v-model"year"value-format"yyyy"type"year":picker-options"disabledCli"placeholder"选择年"> </el-date-picker>data() {return {disabledCli: {/…

Android SDK 上手指南|| 第三章 IDE:Android Studio速览

第三章 IDE&#xff1a;Android Studio速览 Android Studio是Google官方提供的IDE&#xff0c;它是基于IntelliJ IDEA开发而来&#xff0c;用来替代Eclipse。不过目前它还属于早期版本&#xff0c;目前的版本是0.4.2&#xff0c;每个3个月发布一个版本&#xff0c;最近的版本…

7-1 选择法排序

分数 20 全屏浏览题目 切换布局 作者 C课程组 单位 浙江大学 本题要求将给定的n个整数从大到小排序后输出。 输入格式&#xff1a; 输入第一行给出一个不超过10的正整数n。第二行给出n个整数&#xff0c;其间以空格分隔。 输出格式&#xff1a; 在一行中输出从大到小有序…

Springboot 实践(4)swagger-ui 测试controller

前文项目操作&#xff0c;完成了项目的创建、数据源的配置以及数据库DAO程序的生成与配置。此文讲解利用swagger-ui界面&#xff0c;测试生成的数据库DAO程序。目前&#xff0c;项目swagger-ui界面如下&#xff1a; 以”用户管理”为例&#xff0c;简单讲述swagger-ui测试数据库…

WPF入门到精通:2.WPF常用控件及布局

WPF&#xff08;Windows Presentation Foundation&#xff09;是一个用于构建 Windows 应用程序的框架&#xff0c;它提供了丰富的控件和布局方式&#xff0c;帮助开发者快速构建出现代化的应用程序。 WPF常用控件 Button 控件 WPF 中最常用的控件之一。它由一个文本标签和一个…

flinksql实时统计程序背压延迟优化

问题&#xff1a; flinkcdcflinksql做实时读取sls日志和实时统计业务指标&#xff0c;今天发现程序背压了&#xff0c;业务延迟了6个小时。解决办法&#xff1a; 1、资源优化 作业并发大时&#xff1a;在作业的高级配置的资源配置中&#xff0c;增加JobManager的资源&#xf…

MySQL系统变量 会话变量,用户变量

系统变量 分类 全局系统变量需要添加 global 关键字&#xff0c;有时把全局系统变量简称 全局变量 会话系统变量需要添加 session 关键字&#xff0c;有时也把会话系统变量称为 local 变量 局部变量 如果不写&#xff08;global、session&#xff09;默认会话级别。 静态变量在…

在云服务器上安装Jenkins

说明&#xff1a;Jenkins是一个部署项目的平台&#xff0c;通过Jenkins可以省去从项目开发–>部署项目之间的所有流程&#xff0c;做到代码提交即上线。本文介绍在云服务CentOS上安装Jenkins。 前提 安装Jenkins之前&#xff0c;先要在云服务上安装JDK、Maven、Git&#x…

07_缓存预热缓存雪崩缓存击穿缓存穿透

缓存预热&缓存雪崩&缓存击穿&缓存穿透 一、缓存预热 提前将数据从数据库同步到redis。 在程序启动的时候&#xff0c;直接将数据刷新到redis懒加载&#xff0c;用户访问的时候&#xff0c;第一次查询数据库&#xff0c;然后将数据写入redis 二、缓存雪崩 发生情…

Docker搭建LNMP运行Wordpress平台

一、项目1.1 项目环境1.2 服务器环境1.3 任务需求 二、Linux 系统基础镜像三、Nginx1、建立工作目录2、编写 Dockerfile 脚本3、准备 nginx.conf 配置文件4、生成镜像5、创建自定义网络6、启动镜像容器7、验证 nginx 四、Mysql1、建立工作目录2、编写 Dockerfile3、准备 my.cnf…

Azure虚拟网络对等互连

什么是Azure虚拟网络对等互联 Azure虚拟网络对等互联&#xff08;Azure Virtual Network peering&#xff09;是一种连接两个虚拟网络的方法&#xff0c;使得这两个虚拟网络能够在同一地理区域内进行通信。它通过私有IP地址在虚拟网络之间建立网络连接&#xff0c;不论是在同一…

信安通用基础知识

文章目录 密码学经典误区PGP优良保密协议信安经典其它安全手段XSS与CSRF cross site request forgeryCSRF的利用逻辑CSRF示例CSRF防范检查Referer字段添加校验token XSS cross site scripting common weakness enumeration常见密码api误用&#xff08;摘自毕设参考文献&#xf…

Unity VR:XR Interaction Toolkit 输入系统(Input System):获取手柄的输入

文章目录 &#x1f4d5;教程说明&#x1f4d5;Input System 和 XR Input Subsystem&#xff08;推荐 Input System&#xff09;&#x1f4d5;Input Action Asset⭐Actions Maps⭐Actions⭐Action Properties&#x1f50d;Action Type (Value, Button, Pass through) ⭐Binding …

Error creating bean with name ‘esUtils‘ defined in file

报错异常&#xff1a; 背景&#xff1a; esUtils在common服务中、启动media服务时候、报这个异常、后排查esUtils在启动时候发生异常引起的、在相关bean中加入try{}catch{}即可解决问题 String[] split url.split(","); HttpHost[] httpHosts new HttpHost[split.…

字符设备驱动实例(PWM和RTC)

目录 五、PWM 六、RTC 五、PWM PWM(Pulse Width Modulation&#xff0c;脉宽调制器)&#xff0c;顾名思义就是一个输出脉冲宽度可以调整的硬件器件&#xff0c;其实它不仅脉冲宽度可调&#xff0c;频率也可以调整。它的核心部件是一个硬件定时器&#xff0c;其工作原理可以用…

微信小程序:函数节流与函数防抖

目录 问题引入&#xff1a; 定义 解决方案&#xff1a;函数节流 一、案例举例 1.页面展示 2.search.wxml标签展示 3.search.js展示 4.结果展示 二、函数节流解决问题 1.函数 2.实例应用 三、函数防抖解决问题 1.函数 2.原理 3.应用场景 4.应用实例 总结 问题引入…

华为云零代码新手教学-体验通过Astro Zero快速搭建微信小程序

您将会学到 您将学会如何基于Astro零代码能力&#xff0c;DIY开发&#xff0c;完成问卷、投票、信息收集、流程处理等工作&#xff0c;还能够在线筛选、分析数据。实现一站式快速开发个性化应用&#xff0c;体验轻松拖拽开发的乐趣。 您需要什么 环境准备 注册华为云账号、实…

unity之Input.GetKeyDown与Input.GetKey区别

文章目录 Input.GetKeyDown与Input.GetKey区别 Input.GetKeyDown与Input.GetKey区别 Input.GetKey 和 Input.GetKeyDown 是 Unity 中用于检测按键状态的两个不同函数。它们之间的区别在于何时触发。 Input.GetKey(KeyCode key): 这个函数会在用户按住指定的键时触发&#xff0…

深度学习|自监督学习、MAE学习策略、消融实验

前言&#xff1a;最近在阅读论文&#xff0c;发现太多机器学习的知识不懂&#xff0c;把最近看的一篇论文有关的知识点汇总了一下。 自监督学习、MAE学习策略、消融实验 自监督学习MAE学习策略消融实验 自监督学习 Pretrain-Finetune&#xff08;预训练精调&#xff09;模式&…

Jmeter生成可视化的HTML测试报告

Jmeter也是可以生成测试报告的。 性能测试工具Jmeter由于其体积小、使用方便、学习成本低等原因&#xff0c;在现在的性能测试过程中&#xff0c;使用率越来越高&#xff0c;但其本身也有一定的缺点&#xff0c;比如提供的测试结果可视化做的很一般。 不过从3.0版本开始&…