首页 > 其他分享 >基础笔记-时空复杂度分析

基础笔记-时空复杂度分析

时间:2024-03-02 18:45:39浏览次数:25  
标签:复杂度 64MB 笔记 循环 内存 时空

C++一秒可以算1e7或者1e8的次数

由数据范围反推算法复杂度以及算法内容 - AcWing

第七章 时空复杂度分析 笔记 - AcWing

 

 

时间复杂度分析

1.纯循环,看几层循环,就是几次方(有些循环不一定,比如双指针,i循环n次,j其实一共只会循环n次,所以复杂度是O(n))

2.递归,看有递归了几层,计算每一层的时间是多少,相乘

3.

 

 

空间:

 

注意,如果题目规定用64MB,那不能用64MB,最多用到50MB就差不多了,函数调用,函数执行,寄存器这些也要内存的

不过有个细节

比如开了1e18的内存,但是如果你不用到1e18那里的话,是不会爆内存的

但是用到了,就会爆了

还可以用程序的方法计算内存

就比如这样

如果只开大内存不用,一般没事,开了之后用了的话,就爆了

 

标签:复杂度,64MB,笔记,循环,内存,时空
From: https://www.cnblogs.com/didiao233/p/18049048

相关文章

  • 《A Hierarchical Framework for Relation Extraction with Reinforcement Learning》
    代码原文地址摘要现有的大多数方法在确定关系类型之前,需要先识别出所有的实体,这样就忽略了实体提及和关系类型之间的交互。本文提出了一种新颖的联合抽取范式,把相关实体看作是关系的参数(首先检测一个关系,然后提取相应的实体作为关系的参数)。本文在这个范式下采用了一个分层......
  • Docker学习笔记-01-ubuntu22.04安装Docker Desktop
    Docker学习笔记-01-ubuntu22.04安装DockerDesktopubuntudocker一、安装前的说明DockerDesktopforLinux和LinuxDockerEngine是两个不同的东西,在使用的时候会有不同,但是有什么不同,我还没有具体去了解,在后面学习使用的时候要注意区分。DockerDesktopforLinux需要Virtual......
  • Living-Dream 系列笔记 第34期
    T1有一个比较秒的trick:虚拟点。对于本题,我们设一虚拟点\(n+1\)表示水源,于是打井的操作即为与点\(n+1\)连边,将点权转为边权。然后跑kruskal即可。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,tot;intfa[331];intw[331];intp[331]......
  • Living-Dream 系列笔记 第33期
    Living-Dream系列笔记强势回归(雾)T1并查集妙妙题。很容易想到一种朴素的贪心策略:对于所以物品按照价格从大到小排序,然后每一个物品,找到最晚的没有卖物品的那一天卖掉此物品。这样贪心的时间复杂度为\(O(\maxd_i\timesn)\),可以通过。考虑如何优化此贪心。可以发现朴素......
  • Living-Dream 系列笔记 第38期
    T1floyd模板。#include<bits/stdc++.h>usingnamespacestd;intn,m;intdp[131][131];voidfloyd(){ for(intk=1;k<=n;k++) for(inti=1;i<=n;i++) for(intj=1;j<=n;j++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);}intmain(){ cin&g......
  • Living-Dream 系列笔记 第46期
    强连通分量(StronglyConnectedComponents,SCC)。强连通:有向图中,\(x,y\)能相互到达。弱连通:有向图中,\(x\)能到\(y\),\(y\)不能到\(x\)(或反之)。强连通分量:有向图\(G\)中一极大子图\(G1\),使得\(G1\)任意两点均强连通,且\(G1\)不可变得更大(不能添加点)。强连通分量要么是......
  • Living-Dream 系列笔记 第43期
    bellman-ford:因为最短路最多\(n\)点\(n-1\)边,则进行\(n-1\)轮操作,每轮枚举\(m\)边进行松弛即可。时间复杂度\(O(nm)\)。spfa:正确的称呼是队列优化的bellman-ford。我们知道,对于一个点,只有它被松弛了,它的邻接点才有可能被松弛。于是我们用队列记录可能被松弛的点,每......
  • Living-Dream 系列笔记 第45期
    负环,即负权环,指在图\(G\)中边权和为负数的一回路。负环的判定一般有两种方式。以下均以\(n\)点\(m\)边的图\(G\)为例。法一:以边为研究对象。注意到最短路边数一定不超过\(n-1\)边,因此维护\(cnt_x\)表示起点到\(x\)的边数,若某一时刻存在\(cnt_x>n-1\)则存在......
  • Living-Dream 系列笔记 第42期
    T1枚举流量对于花费跑dijkstra并取比值的\(\max\)即可。关于为什么枚举流量不一定当前最优的问题,因为最优解的流量总在枚举范围内,所以无需考虑当前是否最优。#include<bits/stdc++.h>usingnamespacestd;intn,m,ans;intdis[100031];boolvis[100031];structEdge{......
  • Living-Dream 系列笔记 第44期
    比赛链接T1\(100\to10\)。错因:01背包转移方程写错,没有取\(\max\)。并查集合并错写成将u,v而非fnd(u),fnd(v)合并。#include<bits/stdc++.h>usingnamespacestd;intn,m,w;intc[10031],d[10031];intfa[10031];intdp[10031];intfnd(intx){return......