计算时间复杂度

时间复杂度与语句被重复执行的次数息息相关。

一、单层循环

单层循环大致可以分为两种,一种是循环体内的语句不影响循环条件的判定。另一种就是循环体内的语句会影响循环条件的判定。

1、循环体内的语句不影响循环条件的判定

这种情况十分常见且简单,比如给数组插入数据。这里不做过多说明。

2、循环体内的语句会影响循环条件的判定

 很明显可以看到,i=i*2会影响i的值,从而影响下一次循环的判定。

我们假设这个语句会循环t次,因为i的初始值为1,所以在循环内i的最终值就是2^{t-1},那么就有2^{t-1}\leq n

所以t\leq 1+\log _{2}n ,所以答案选D。

二、双层循环

双层循环也可以分为以下两种,

1、内层循环条件与外层循环的变量有关

很明显在内层循环里面的j的判定条件与外层循环变量i的值有关。i的值的范围为从n-1到2,j的值的范围为从1到i-1。于是里面对换的次数应该为:\sum_{i=2}^{i=n-1}\sum_{j=1}^{j=i-1}1= \sum_{i=2}^{n-1}i-1最终结果为\frac{\left ( n-1 \right )\left ( n-2 \right )}{2},所以答案选D。所以这种情况就是如果内外层有关,那么就是双重求和。

 这里要注意外层循环的操作语句还会影响外层循环的判定。我们现在只看这一层循环,因为执行第一次的时候i为1,即2^{0},第二次的时候i的值为2,即2^{1}。以此类推,假设这层循环执行t次,那么i的最终值应该为2^{t-1},且2^{t-1}< n。并且注意,第t+1次时循环终止,即i的值为2^{t}。那么肯定就有2^{t}\geq n

而当i每次对应一个值的时候,内层循环就会执行对应的值的次数。那么总循环次数实际就为1+2+4+8+...+2^{t-1}。很明显这是一个等比数列,可以得出最终结果为2^{t}-1。因为2^{t-1}< n\leq 2^{t},给不等式2^{t-1}< n两边同时乘以2,那么就有2^{t}< 2n,则有n< 2^{t}-1< 2n。所以答案选B。

这道题虽然外层循环变量与内层循环条件有关,但是因为i的变化不是线性递增的,它是呈指数级增长的,所以就不能用简单的双重求和来表示。

2、内层循环条件与外层循环的变量无关

在内层循环里面j的判定条件与n有关与外层循环变量i无关,k的范围从1到n,j的范围从1到n。但需要注意的是k的操作语句为k*=2。所以外层循环最多执行t\leq1+ \log _{2}n次。而内层循环执行n次,所以答案选C。所以这种情况就是如果外层不影响内层直接就是两层循环分别算出各自需要的次数然后相乘。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

智慧政务大屏建设方案

智慧政务大屏建设方案是为政府部门提供信息化展示和决策支持的重要工具。下面将提供一个详细的智慧政务大屏建设方案&#xff0c;包括硬件设备、软件平台和功能模块等。 **一、硬件设备** 智慧政务大屏的硬件设备需要满足以下基本要求&#xff1a; 1. 显示屏&#xff1a;选择…

(5)SpringMVC处理携带JSON格式(“key“:value)请求数据的Ajax请求

SpringMVC处理Ajax 参考文章数据交换的常见格式,如JSON格式和XML格式 请求参数的携带方式 浏览器发送到服务器的请求参数有namevalue&...(键值对)和{key:value,...}(json对象)两种格式 URL请求和表单的GET请求会将请求参数以键值对的格式拼接到请求地址后面form表单的P…

基于若依ruoyi-nbcio支持flowable流程增加自定义业务表单(二)

更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码&#xff1a; https://gitee.com/nbacheng/ruoyi-nbcio 演示地址&#xff1a;RuoYi-Nbcio后台管理系统 之前讲了自定义业务表单&#xff0c;现在讲如何与流程进行关联 1、后端部分 WfCustomFormMapper.xml &…

Python并行编程之道—加速海量任务同时执行

这次我要和大家分享一种加速海量任务执行的方法&#xff0c;那就是Python并行编程。如果你经常处理大量的任务&#xff0c;并且希望能够同时执行它们以提高效率&#xff0c;那么并行编程将会给你带来巨大的帮助&#xff01; 1、了解并行编程 并行编程是利用多个执行单元同时执…

Talk | ACL‘23 杰出论文,MultiIntruct:通过多模态指令集微调提升VLM的零样本学习

本期为TechBeat人工智能社区第536期线上Talk&#xff01; 北京时间10月11日(周三)20:00&#xff0c;弗吉尼亚理工大学博士生—徐智阳、沈莹的Talk已准时在TechBeat人工智能社区开播&#xff01; 他们与大家分享的主题是: “通过多模态指令集微调提升VLM的零样本学习”&#xff…

段码屏学习

文章目录 1.液晶屏和OLED屏2.液晶屏原理3.码段屏原理4.单色点阵屏原理5.彩色点阵屏原理6.HT1621驱动LCD段码屏 1.液晶屏和OLED屏 答&#xff1a; 液晶屏&#xff1a;码段屏、单色点阵屏、彩色点阵屏。 OLED屏&#xff1a;消费类电子产品多&#xff0c;贵。 2.液晶屏原理 …

安卓玩机----展讯芯片机型解锁 读写分区工具 操作步骤解析

国内机型大都使用高通和MTK芯片。展讯芯片使用的较少。相对来说高通和mtk机型解锁以及读取分区工具较多。展讯的几乎没有。目前有大佬开发出了一款展讯芯片解锁 与读写分区工具.开源的tools 官方分享说明&#xff1a; 是一款专为 Windows 计算机设计的免费、用户友好的工具&am…

应用商店优化的好处有哪些?

应用程序优化优势包括应用在商店的可见性和曝光度&#xff0c;高质量和被相关用户的更好发现&#xff0c;增加的应用下载量&#xff0c;降低用户获取成本和持续增长&#xff0c;增加应用收入和转化率以及全球受众范围。 1、提高知名度并在应用商店中脱颖而出。 如果用户找不到…

(六)Python流程控制

和其它编程语言一样&#xff0c;按照执行流程划分&#xff0c;Python 程序也可分为 3 大结构&#xff0c;即顺序结构、选择&#xff08;分支&#xff09;结构和循环结构&#xff1a; Python 顺序结构就是让程序按照从头到尾的顺序依次执行每一条 Python 代码&#xff0c;不重复…

C++11新特性(右值引用,万能转发)

这篇文章是C的重中之重&#xff0c;通过这篇文章你能体会到C/C大佬们对性能的极致追求&#xff0c;你能感受到独属C/C人的浪漫&#xff0c;对高消耗的零容忍&#xff0c;对高性能的不倦探索。右值引用是由Scott Meyers在他的著名书籍《Effective C》中提出的&#xff0c;因为其…

开山之作 | YOLOv1算法超详细解析(包括诞生背景+论文解析+技术原理等)

前言&#xff1a;Hello大家好&#xff0c;我是小哥谈。目标检测是计算机视觉领域的一项重要研究方向&#xff0c;它在许多应用领域中都得到了广泛应用&#xff0c;如人脸识别、物体识别、自动驾驶、视频监控等。在过去&#xff0c;目标检测方法主要采用基于RCNN、Fast R-CNN等深…

试过GPT-4V后,微软写了个166页的测评报告,业内人士:高级用户必读

一周之前&#xff0c;ChatGPT迎来重大更新&#xff0c;不管是 GPT-4 还是 GPT-3.5 模型&#xff0c;都可以基于图像进行分析和对话。与之对应的&#xff0c;多模态版GPT-4V模型相关文档也一并放出。当时 OpenAI 放出的文档只有18页&#xff0c;很多内容都无从得知&#xff0c;对…

【Redis】Redis性能优化:理解与使用Redis Pipeline

原创不易&#xff0c;注重版权。转载请注明原作者和原文链接 文章目录 Pipeline介绍原生批命令(MSET, MGET) VS PipelinePipeline的优缺点一些疑问Pipeline代码实现 当我们谈论Redis数据处理和存储的优化方法时&#xff0c;「 Redis Pipeline」无疑是一个不能忽视的重要技术。…

Kelper.js 笔记 python交互

1 加载Kepler 地图 KeplerGl() 1.1 主要参数 height 可选 默认值&#xff1a;400 地图显示的高度 data 数据集 字典&#xff0c;键是数据集的名称 config地图配置字典 1.2 举例 from keplergl import KeplerGlmap_KeplerGl() map_ 默认的位置 1.3 添加自己的图 1.3.1 读…

玩转Linux Shell Terminal Tmux

一、Shell编程☘️ 1. Shell指令快捷操作 1. echo # 系统指令 $ echo $(pwd) # 对于系统自带的pwd&#xff0c;此处不能写echo $pwd# 自定义变量 $ foo$(pwd) $ echo $foo # 不同于pwd&#xff0c;对于自定义的foo&#xff0c;不能用$(foo)2. !! # 假设你先执行了以下原本…

再一次整理一下spring框架步骤

1.pom.xml依赖 2.applicationbean.xml 3.类 小树叶可以跟bean联动起来 不写接口直接写类 实现类 4.测试 两种方法的实现

python结合excel数据轻松实现接口自动化测试

在刚刚进入测试行业的时候&#xff0c;最开始也是做功能测试&#xff0c;我想很多伙伴和我一样&#xff0c;觉得自动化测试都很高端&#xff0c;很神秘。迫不及待的想去学习作自动化测试。 以前比较常用数据库python做自动化&#xff0c;后面发现excel个人觉得更加适合&#x…

麒麟操作系统提示“默认密钥环已上锁”的解决办法

在国产麒麟操作系统上,有的时候不知道为啥,打开vscode或者其他应用软件时,总是提示“密钥环已上锁”,该怎么处理呢? 需要点击“开始”,在搜索框中输入“password” 点击打开“密码和密钥”,看到如下图。 然后点击左上角的箭头,回退,打开如下图:

java中对象的比较

文章目录 一、 PriorityQueue中插入对象二、元素的比较2.1 基本类型的比较2.2 引用类型比较 三、对象的比较3.1 覆写基类的equals3.2 基于Comparble接口类的比较3.3 基于比较器比较3.4 三种方式对比 四、 集合框架中PriorityQueue的比较方式五、使用PriorityQueue创建大小堆&am…

更新 | 持续开源迅为RK3568驱动指南第十二篇-GPIO子系统

《iTOP-RK3568开发板驱动开发指南》更新&#xff0c;本次更新内容对应的是驱动&#xff08;第十二期_GPIO子系统-全新升级&#xff09;视频&#xff0c;后续资料会不断更新&#xff0c;不断完善&#xff0c;帮助用户快速入门&#xff0c;大大提升研发速度。 文档教程更新至第十…