寒假训练 第一节 时空复杂度分析

2023-11-14

算法是由若干条指令所组成的的有穷序列,其中每一条指令表示计算机的一个或多个操作。

一个好的算法首先要具备正确性、可读性和健壮性。在具备这三个条件后,就应该考虑算法的效率问题。即算法的时间效率和空间效率两方面。

时间复杂度

一个算法所需要的运算时间通常与解决问题的规模大小有关。问题规模就是一个和输入有关的量,用n来表示问
题的规模的量,通常把算法运行的时间T表示为n的函数,记作T(n)。不同的算法随着n的变化运算时间也不相同。
当n逐渐增大时T(n)的极限情况,一般称为时间复杂度。
当我们讨论一个程序运行时间时,注重的不是T(n)的具体值,而是它的增长率。T(n)的增长率与算法中数据的
输入规模有关,而数据的输入规模往往用法中的某个变量函数来表示通常我们用f(n)。随着数据输入的增大,
f(n)的增长率与T(n)的增长率接近。因此T(n)和发f(n)在数量级上是一致的记作:

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

计算时间复杂度
1.忽略常数项。 ( 例1:n10 +3 ===> n10)
2.忽略系数。( 例2:3n10 ===> 3n10
3.只保留最高项。 ( 例3:n10 + n9 ===> n10

常见的时间复杂度的大小顺序:
从小到大依次是:O(1)<O(log2n)<O(n)< O(nlog2n)<O(n2)<O ( n^3 ^) <O(2n)

例题1:P8780 [蓝桥杯 2022 省 B] 刷题统计

理论上无法得满分

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
		 long long  a,b,n,x= 0,day=1,ans = 0;
	 cin>>a>>b>>n;
	 while(x<n){   
	 	if(day == 6 || day == 7) {
	 		x += b;
	 		ans++;
		}else{
			x+= a;
			ans ++;
		}if(day >7){
			day = 1;
		}
	 	day++;
	 }
	 cout<<ans;

return 0;
}

分析:
根据要求:
在这里插入图片描述
对于100%的数据 要求在1-1018 ,我们考虑最坏的情况:a和b均为1时且 n=1018;在最坏的情况下无法满足对于100%的数据 要求在1-1018 。但是上面的解法依旧能AC,这个题的测试点数据均落在来了1-106。正常来说上面的解法无法取得100分;

正确的写法:

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	long long a,b,n,x,num,ans;
	cin>>a>>b>>n; 
//	一个星期的做题量 
	x = 5*a+b*2;
	if(n%x == 0){
		ans = n/x*7;
	}else{
//做了n/x个学期*7=(n/x)星期一个做了多少题 
		ans = n/x*7;
//		剩余的题量  
		n = n -n/x*x;
		for(int i=1;i<=7;i++){
			if(i == 6||i == 7){
				n-=b;
			}else{
				n-=a; 
			}
			if(n<=0){
				ans+=i;
				break;
			}
		}
	}
	cout<<ans;
return 0;
}

例题2:P2249 【深基13.例1】查找

在这里插入图片描述

如果直接用暴力for循环来做毋庸置疑一定会超时,根据题目所说:输入 n个不超过 109
的单调不减的非负整数。说明在此我们可以使用二分查找。
如果使用for循环,当 n = 109 时 时间复杂度为 :O(n) = 109;总体上会超时;
但是二分查找的时间复杂度为:O(log2n) 带入 n = 109 得 log2109 < 109

空间复杂度

覃神说:绝大多数情况下不会卡,没啥用。
所以这里可以偷懒不写了!!!

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

寒假训练 第一节 时空复杂度分析 的相关文章

  • TAS-LR 论文辅助笔记 & 图拉普拉斯正则项推导

    1 图拉普拉斯正则项的直观目标函数 我们已知一张图G的邻接矩阵A 和度矩阵D 那么我们就知道他的拉普拉斯矩阵L D A 在使用矩阵分解的时空数据补全问题中 有一些文献使用图拉普拉斯正则化项来对空间特征矩阵进行约束 我们假设低秩的空间特征矩阵
  • 2021-12-23 工作记录--LayUI-单击行内容展示子表(手风琴效果),堪称yyds

    LayUI 单击行内容展示子表 手风琴效果 百度了好多办法 都不能达到这种效果 所以记录一下 最开始使用layui soul table 但是它不能实现单击行内容展示子表 而是单击行最左列展示子表 所以与项目不符 则放弃了 但是感兴趣的小萝
  • 幼儿园里面有科技设备么

    现代社会 幼儿园是孩子们是快乐且有意义的生涯起点 他们从这里认识世间万物 格物斯坦心系每位的热爱人工智能的孩子们 祖国的未来就靠你们了 幼儿园的核心工作是保证幼儿健康成长 同时需要为幼儿提供良好的学习和生活环境 随着现代技术正朝着智能化的方
  • Rocketmq Filter 消息过滤(TAGS、SQL92)原理详解 & 源码解析

    1 背景 1 1 Rocketmq 支持的过滤方式 Rocketmq 作为金融级的业务消息中间件 拥有强大的消息过滤能力 其支持多种消息过滤方式 表达式过滤 通过设置过滤表达式的方式进行过滤 TAG 根据消息的 tag 进行过滤 SQL92

随机推荐

  • 【 ROS 入门 2】tf 入门学习教程总结(缺少系统整理)

    ROS官网 tf 教程 http wiki ros org tf Tutorials 参考博客 三维旋转矩阵 包括任意轴的通用旋转矩阵 Euler角 单位四元数 的计算 视觉SLAM中的数学基础 第二篇 四元数 ROS学习 轻松使用tf t
  • PIL,cv2,plt的使用与区别

    PIL cv2 plt的使用与区别 1 比较三者的打开图片 显示图片 打开的图片的类型 2 图像类型的转换 PIL与numpy 3 PIL cv2 plt混用 3 1 cv2 plt读PIL打开的图像 3 2 PIL plt读cv2打开的图
  • https 是如何保护数据传输的

    为什么需要 https https 是 http ssl 也就是加密的 http 数据传输 我们都知道 https 的最主要的作用在于保证数据的安全 但具体来说 https 的安全性主要体现在以下两点 保证数据传输不被中间人盗用和信息的泄漏
  • GitHub开源协议

    开源协议 有名开源许可证 很多 经过Open Source Initiative组织 OSI批准 通过批准的开源协议目前有58种 常见的开源许可证包括 MIT MIT License GPL GNU General Public Licen
  • 预览word文件,支持下载(微软提供)

    预览打印 file 文件对象 url 接口地址 filepath 文件路径 filetype 文件类型 PS 兼容docx pdf后缀文件 export const filePreview file gt if file filepath
  • 三层架构:软件设计架构

    1 界面层 表示层 用户看的得界面 用户可以通过界面上的组件和服务器进行交互 2 业务逻辑层 处理业务逻辑的 3 数据访问层 操作数据存储文件
  • ---复位现象---GD32 MCU插入SD卡MCU立刻复位

    问题描述 程序运行正常 但是在插入SD卡的瞬间 单片机硬件复位 程序重新运行 之后状态一切正常 可以读取到SD卡 如果上电前插入SD卡 则一切正常 原因 使用示波器测试MCU电源 在SD卡插入瞬间 MCU电源电压跌落到2 5V以下 正常GD
  • 重载输入<<,输出>>,前置和后置++,--运算符

    由于系统给定的输入 lt lt 输出 gt gt 前置和后置 运算符只能处理类似于int float等系统已经定义好的类型的变量 为了能对我们自己定义的类的对象也能进行这些操作 我们就要重载这些运算符 定义一个复数类的对象 class Co
  • 基于OPENCV4的火焰烟雾检测

    现在目标检测主要采用深度学习训练模型 然后采用OPENCV4调用 烟雾火焰检测 采用CAFFE训练一个模型 采用OPENCV4调用 C PYTHON都可以调用 可以加Q 2830025146进行讨论 效果测试在 https download
  • 前端安全

    有哪些可能引起前端安全的问题 跨站脚本攻击 Cross Site Scripting XSS 一种代码注入方式 为了与 CSS 区分所以被称为 XSS 早期常见于网络论坛 起因是网站没有对用户的输入进行严格的限制 使得攻击者可以将脚本上传到
  • 行人重识别数据集汇总

    最近一段时间在做行人重识别方向的研究 行人重识别 Person Re Identification 作为图像识别领域的一个分支 在实际生活中具有极其重要的意义 目前 城市里的用于公共治安领域的摄像头已经大量部署 几乎到了几十米到几百米一个覆
  • Android 11(targetSdkVersion 30)不能获得存储权限的问题和适配指南

    虽然原文说的比较详细了 但我补充一两点 也为了方便自己总结和避坑 Android权限大致可分为三类 普通权限 只需要在清单文件中注册即可 危险权限 需要在代码中动态申请 以弹系统 Dialog 的形式进行请求 特殊权限 需要在代码中动态申请
  • 苹果新iPad创新乏力,中国发售遇冷失宠

    7月20日清晨 北京三里屯苹果店外有点冷清 十几个顾客在门口安静地排着队 曾经活跃的黄牛党没了踪影 守候在一旁的工作人员正在拆除原本打算维持秩序的护栏 如果不是店面上巨大的苹果标志 你恐怕很难把这个场景和苹果新品首发联系在一起 要知道在半年
  • 测试用例入门(三)-使用边界值分析法编写测试用例

    在 软件测试 一书中是这样描述边界值分析法的作用 如果在悬崖峭壁边可以自信 安全的行走而不掉下去 平地就不在话下了 本篇文章中的演示代码均由Python编写 目录 一 边界值分析法概述 二 边界条件的判断 三 边界两侧的判断 四 次边界条件
  • 输入华氏温度输出摄氏温度

    华氏温度转化为摄氏温度 c 5 9 f 32 数据 输入华氏温度 f 输出摄氏温度 c f int input 请输入华氏度 c f 32 5 9 print 6 2f华氏度对应的摄氏度为 6 2f f c 中间出过一点小问题 比如第一行双
  • input标签的类型

    今天学习突然想着input有哪些类型呢 然后就查了下资料 记录一下 1 文本框 type text 2 密码框 type password 3 单选框 type radio 4 复选框 type checkbox 5 图片上传 type f
  • linux切换用户时报错 this account is currently not available

    linux切换用户时报错 this account is currently not available 在安装完redis之后系统创建了一个名叫redis用户 但切换到这个用户的时候却报了错 this account is current
  • 网站怎么创建?

    网站怎么创建 现在很多公司企业都会有自己的网站 即使是没有网站的公司也抓紧时间纷纷入局 希望能在互联网的流量中分到一杯羹 那么网站怎么创建呢 下面给大家简单说一说 网站怎么创建步骤1 首先我们准备好一个域名 一个网站需要有域名才能访问 我们
  • 论文笔记:DEEP DECLARATIVE DYNAMIC TIME WARPING FOREND-TO-END LEARNING OF ALIGNMENT PATHS

    个人感觉 可微DTW的主要优点作为一个损失函数 可以进行梯度反向传播 如果目标只是两个时间序列的相似度 可能不太需要 1 Intro 1 1 背景 DTW 笔记 Dynamic Time Warping 动态时间规整 DTW的python实
  • 寒假训练 第一节 时空复杂度分析

    算法是由若干条指令所组成的的有穷序列 其中每一条指令表示计算机的一个或多个操作 一个好的算法首先要具备正确性 可读性和健壮性 在具备这三个条件后 就应该考虑算法的效率问题 即算法的时间效率和空间效率两方面 时间复杂度 一个算法所需要的运算时