【2022统考真题】计算时间复杂度

目录

一、题目描述

二、思路分析

三、易错提醒

四、同级和嵌套的关系

一、题目描述

下列程序段的时间复杂度是()

int sum = 0;
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;

A. O(logn)

B. O(n)

C. O(nlogn)

D. O(n^2)

二、思路分析

首先我们先对外层循环进行分析:

外层每循环一次,i=i*2

即:i*2*2*2*2*2*...*2=n

每乘以一次2,代码执行一次;共乘了多少次2,就代表代码执行了多少次

设共执行了x次,所以:2^x=n

即x=logn

所以外层循环的时间复杂度为:O(logn)


接下来看内层循环:

我们发现,内层j的循环次数是基于外层i的值

由于j<i,每当外层循环迭代器一次,内层的循环次数就是i-1

因为i是呈指数的形式增长的

外层第一次执行循环:i=1=2^0

外层第二次执行循环:i=1=2^1

外层第三次执行循环:i=1=2^2

外层第四次执行循环:i=1=2^3

......

所以外层循环迭代器第k次的时候,i的值大概是2^(k-1)

所以外层循环第k次时,内层循环执行2^(k-1)-1次。

内层的总执行次数就是:1+2+4+8+......+2^(k-1)-1

这里求出的内层执行次数的总和,也就是内外层执行的次数

其实就是一个等比数列

等比数列求和公式有两种,当q!=1的时候,Sn=a1(1-q^n)/1-q  or  Sn=(a1-an*q)/1-q

因为k=logn

所以:

Sn= 1 * (1 - 2^(k-1))  / (1 - 2) = (2^k-1)  = 2^(logn-1) 

忽略掉1,则2^(logn-1) =n

时间复杂度为:O(n)

综上所B述:答案为B

三、易错提醒

  1. 为什么求出内层总循环次数就是求出总执行次数?
  2. 循环嵌套不该是内层循环次数*外层循环次数吗?
  3. 那外层明明也执行了,那不该把外层执行次数与内层执行次数相加吗?

这是我在写这道题碰壁的三个点。

个人见解如下:

3.1 内层总循环次数就是总执行次数的原因

在之前写代码,我们遇见过这种类型的代码:

int sum = 0;
for (int i = 0; i < n; i++)
{for (int j = 0; j < n; j++){sum++;}
}

我们知道,它的时间复杂度是:O(n^2)

那为什么是O(n^2)呢?

那就结合图来进行详细分析一下:

所以说,内层总循环次数就是求出了总执行次数。


3.2 是否可以内外层简单相乘的情况

那为什么图1代码求的方式是外层*内层即可,而图2却不能外层*内层?也就是n*logn?

简单分析来看:

  1. 因为图1的代码循环终止条件是相互不关联的,都是为n,所以可以进行简单的相乘来进行。
  2. 而图2的代码终止条件是具有关联性的,内层的循环次数取决于外层i的值,所以要逐步分析出当外层执行一次,内层循环次数的变化,并把内层相加。


3.3 内外层执行次数是否需要相加

那外层明明也执行了,那不该把外层执行次数与内层执行次数相加吗?

结合图进行分析:

那为什么求时间复杂度求最深层语句即可,不需要加上最外层的执行次数?

因为当n取很大值的时候,cpu运行速度很快,那些较小的数值就可以忽略不计,只需要计算属于哪个量级即可。

当n很大时,图3的n^2远远大于n ,可以忽略n,所以时间复杂度为O(n^2)

图4的n远远大于logn,可以忽略logn,所以时间复杂度为O(n)

因为时间复杂度本质是计算算法的执行次数属于哪个量级!!!

故而,我们解决了以上的三个问题!

四、同级与嵌套的关系

同级关系相加    嵌套关系相乘

我们对比以下两段代码:

代码一

//嵌套
int n = 10;
int sum = 0;
for (int i = 0; i < n; i++)
{for (int j = 0; j < n; j++){sum++;}
}

代码二

//同级
int n = 10;
int sum = 0;
for (int i = 0; i < n; i++)
{sum++;
}
for (int j = 0; j < n; j++)
{sum++;
}
cout << sum << endl;

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

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

相关文章

前端转换double数据,保留两位小数

Number Number(1.00) 1 Number(1.10) 1.1 Number(1.101) 1.101 要想前端展示页面按 1.00展示1&#xff0c;1.10 展示1.1 需要套一个number() 1.1 保留两位小数&#xff0c;并三位一个分隔符 indexView.value[key] formatNumber(indexView.value[key].toFixed(2))//格式…

聚类分析 | WOA-K-means++聚类优化算法

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 (创新)WOA-K-means聚类优化算法 (WOA聚类优化&#xff0c;创新&#xff0c;独家) 鲸鱼算法优化K-means聚类优化算法 matlab语言&#xff0c;一键出图&#xff0c;直接运行 1.鲸鱼算法WOA作为群智能算法简单高效&a…

25.2 采集端高基数的现象和原因

本节重点介绍 : 什么是高基数采集端高基数的原因 标签的值过多 获取采集端的高基数metrics tsdb-status页面介绍统计原理讲解&#xff1a;是基于内存中的倒排索引 算最大堆取 top10通过接口获取metrics name top10 什么是高基数 通俗的说就是返回的series或者查询到的serie…

spring boot itext7 修改生成文档的作者、制作者、标题,并且读取相关的信息。

1、官方的example文件&#xff1a;iText GitHub itext-java-7.2.5\kernel\src\test\java\com\itextpdf\kernel\pdf\PdfStampingTest.java 2、修改代码&#xff1a; Testpublic void stamping1() throws IOException {String filename1 destinationFolder "stamping1_…

【安装教程】Windows10环境下Pytorch(GPU版)的安装与配置

目录 Pytorch的概念安装前要求一、NVIDIA驱动查看二、Anaconda的安装2.1 Anaconda的安装2.2 创建虚拟环境2.3 激活虚拟环境 三、CUDA ToolKit的安装&#xff08;选做&#xff0c;CPU版本可跳过&#xff09;3.1 CUDA安装包的下载&#xff08;以CUDA11.6.0为例&#xff09;3.2 CU…

【兼容多端】UNIAPP popper气泡弹层vue3+typescript unibest

最近要实习一个泡泡弹层。看了下市场的代码&#xff0c;要么写的不怎么好&#xff0c;要么过于复杂。于是拿个轮子自己加工。200行代码撸了个弹出层组件。兼容H5和APP和小程序。 功能&#xff1a; 1)只支持上下左右4个方向的弹层不支持侧边靠齐 2)不对屏幕边界适配 3)支持弹层…

EmEditor传奇脚本编辑器

主程序&#xff1a;EmEditor.exe 目前已有功能 可以自己指定一个快捷键 实现以下功能&#xff08;默认快捷键为&#xff1a;F1&#xff09; 以下全功能 都是鼠标所在行 按快捷键 &#xff08;默认快捷键&#xff1a;F1&#xff09; 1.在Merchant.txt中 一键打开NPC 没有…

注册安全分析报告:惠农网

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…

C语言 | Leetcode C语言题解之第462题最小操作次数使数组元素相等II

题目&#xff1a; 题解&#xff1a; static inline void swap(int *a, int *b) {int c *a;*a *b;*b c; }static inline int partition(int *nums, int left, int right) {int x nums[right], i left - 1;for (int j left; j < right; j) {if (nums[j] < x) {swap(…

前端的AI工具:ChatGPT Canvas与Claude Artifacts对比 -仅仅是OpenAI一个迟来的追赶吗?- 贺星舰五飞试验成功

如果你对OpenAI的ChatGPT Canvas和Anthropic的Claude Artifacts有所耳闻&#xff0c;可能会想知道这两个工具有何不同&#xff0c;以及哪个能让你的工作流程更加顺畅。这两个工具旨在提升生产力&#xff0c;但侧重点各异——编码、写作、创意和实时反馈。 本文将深入探讨ChatG…

面腾讯后台开发,二面挂掉了,,,

随着各厂秋招的开启&#xff0c;收到面试邀请的同学也越来越多。在当年和我一起找实习的同学里面&#xff0c;有实力较强的同学收到了腾讯后台开发的校招面试邀请。但面试不止是实力的竞争&#xff0c;也有很重要的运气的因素。 虽然我的同学在腾讯后台开发的二面中挂掉了&…

76.最小覆盖子串

题目:76. 最小覆盖子串 - 力扣&#xff08;LeetCode&#xff09; 代码思路: (滑动窗口) O(n) 这道题要求我们返回字符串 s中包含字符串 t 的全部字符的最小窗口&#xff0c;我们利用滑动窗口的思想解决这个问题。因此我们需要两个哈希表&#xff0c;hs哈希表维护的是s字符串中…

QT:“提升为“使用(自定义控件)

目录 一.步骤与作用 1.步骤 2.作用 二.使用 1.mainwindow.ui ->拖一个 Push Button 控件到画布->右击Push Button弹出对话框->单击"提升为" 2.输入提升类名称MyButton->点击添加 3.选择基类名称为QPushButton,点击提升 4.新建MyButton文件 5.在…

初等数学几百年重大错误:将根本不是无穷集的真子集误为其真子集

黄小宁 【摘要】长为1的直线段形橡皮筋A拉长为长为2的橡皮筋B&#xff08;可二等分&#xff09;&#xff0c;去掉拉力使B缩短成原来的A&#xff0c;A不是B的一半。同样可证直线段L均匀压缩变短为直线段D&#xff5e;L不能成为L的一部分。数学一直误以为D是L的一部分使康脱推出…

《RabbitMQ篇》消费者轮询消费消息

当有多个消费者都在同一个队列中拿取消息时&#xff0c;会轮询从队列中拿取消息消费。 RabbitMQUtil类为工具类&#xff0c;获取Channel。 import com.rabbitmq.client.Channel; import com.rabbitmq.client.Connection; import com.rabbitmq.client.ConnectionFactory;public…

HBuilder X 下载vue-router时 发生异常:npm ERR! code EPERM

一、异常 PS C:\Users\GL\Documents\HBuilderProjects\vj1> npm i vue-router3.6.5 npm ERR! code EPERM npm ERR! syscall mkdir npm ERR! path C:\Program Files\nodejs\node_cache\_cacache npm ERR! errno EPERM npm ERR! FetchError: Invalid response body while tr…

【Linux】来查看当前系统的架构

使用 uname 命令 uname -m 使用 arch 命令 arch 查看 /proc/cpuinfo 文件 查找 model name 或 Processor 字段。 cat /proc/cpuinfo 使用 lscpu 命令 lscpu

一些NLP代表性模型

&#xff08;一&#xff09;BERT 由Bidirectional Encoder Representations from Transformers的首字母组成&#xff0c;是encoder-only结构类型的代表。 模型分预训练和微调两步&#xff0c;预训练任务有两类&#xff1a;masked language model(MLM)、next sentence predict…

构造函数

引入&#xff1a;构造函数的由来 对于以下Date类&#xff1a; class Date { public:void Init(int year, int month, int day){year year;_month month;_day day;}void Print(){cout << _year << "-" << _month << "-" <&…

《自然语言处理NLP》—— 词嵌入(Word Embedding)及 Word2Vec 词嵌入方法

文章目录 一、词嵌入介绍1.示例介绍2.词嵌入的主要特点3.常见的词嵌入方法3.词嵌入的应用 二、Word2Vec 词嵌入方法1. 连续词袋模型&#xff08;CBOW&#xff09;2. Skip-gram模型3.Word2Vec方法的应用 在了解词嵌入之前需要了解什么是 独热编码&#xff08;One-Hot Encoding&…