Memory Limit Exceeded(内存超限)

2024-03-20 22:32

本文主要是介绍Memory Limit Exceeded(内存超限),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Memory Limit Exceeded(内存超限)

出现超内存时我们需要对自己的程序的空间复杂度进行优化,此处的空间复杂度是与时间复杂度相对应的。

空间复杂度:

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。      

类似于 [1]  时间复杂度的讨论,它也是问题规模n的函数。

一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间算法的输入输出数据所占用的存储空间算法在运行过程中临时占用的存储空间这三个方面。

存储算法本身所占用的存储空间:与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。

算法的输入输出数据所占用的存储空间:是由要解决的问题(问题规模)决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。

算法在运行过程中临时占用的存储空间:随算法的不同而异。    (来自百度百科)

分析空间复杂度:

算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为O(log2n);当一个算法的空间复杂度与n成线性比例关系时,可表示为O(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。        (来自百度百科)

避免的方法:

只能是跟据题目所给出的数据范围,看一看数组开辟的能不能再小一些,或者更改算法以使用更小的内存。

 

其它莫名导致MLE的题:

1.     做字典树,AC自动机

        把存树结点的数组,在init()初始化函数中一次性清零。MLE。。。

        

    void init()  //初始化{while(!qu.empty())qu.pop();mem(ne, 0);     //所用数组一次性清零mem(fail,0);mem(vis,0);mem(book,0);tot=1;}void Insert(char *str,int y)  //插入字符串{int ls=strlen(str);int rt=0;for(int i=0; i<ls; i++){int x=str[i];   //把字符串的字符存入字典树if(!ne[rt][x])ne[rt][x]=tot++;  //若这一字符没有在这一分支 ,节点数+1;rt=ne[rt][x];}vis[rt]=y+1;//   printf("stateT_cnt==%d\n",stateT[rt].cnt);}

        要在建树的时候一个一个清零。。。 就是要保证只清零了要用的点; AC

       

void init()  //初始化{while(!qu.empty())qu.pop();mem(ne[0], 0);   //fail[0]=-1;tot=1;}void Insert(char *str,int y)  //插入字符串{int ls=strlen(str);int rt=0;for(int i=0; i<ls; i++){int x=str[i];   //把字符串的字符存入字典树if(!ne[rt][x]){mem(ne[tot],0);   //建树时清零,保证要用的数据点清零fail[tot]=-1;ne[rt][x]=tot++;  //若这一字符没有在这一分支 ,节点数+1;}rt=ne[rt][x];}vis[rt]=y;//   printf("stateT_cnt==%d\n",stateT[rt].cnt);}

2. 数学题  (Smith Numbers)

vector<int>ve;     在get_s函数里可以调用gt_n函数;  没调用get_n函数直接在get_s函数又写一遍,结果MLE

ll get_n(ll x)
{ll ans=0;while(x){ans += x%10;x/=10;}return ans;
}
ll get_s(ll x)
{ll ans=0;prime_decompose(x);for(ll i=0;i<ve.size();i++){// printf("ve%d ",ve[i]);while(ve[i]){ans += ve[i]%10;ve[i] /= 10;}}return ans;
}

调用了的,AC

ll get_n(ll x)
{ll ans=0;while(x){ans += x%10;x/=10;}return ans;
}
ll get_s(ll x)
{ll ans=0;prime_decompose(x);for(ll i=0;i<ve.size();i++){ans+=get_n((ll)ve[i]);   //直接调用}return ans;
}

 

这篇关于Memory Limit Exceeded(内存超限)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/830964

相关文章

NameNode内存生产配置

Hadoop2.x 系列,配置 NameNode 内存 NameNode 内存默认 2000m ,如果服务器内存 4G , NameNode 内存可以配置 3g 。在 hadoop-env.sh 文件中配置如下。 HADOOP_NAMENODE_OPTS=-Xmx3072m Hadoop3.x 系列,配置 Nam

JVM内存调优原则及几种JVM内存调优方法

JVM内存调优原则及几种JVM内存调优方法 1、堆大小设置。 2、回收器选择。   1、在对JVM内存调优的时候不能只看操作系统级别Java进程所占用的内存,这个数值不能准确的反应堆内存的真实占用情况,因为GC过后这个值是不会变化的,因此内存调优的时候要更多地使用JDK提供的内存查看工具,比如JConsole和Java VisualVM。   2、对JVM内存的系统级的调优主要的目的是减少

JVM 常见异常及内存诊断

栈内存溢出 栈内存大小设置:-Xss size 默认除了window以外的所有操作系统默认情况大小为 1MB,window 的默认大小依赖于虚拟机内存。 栈帧过多导致栈内存溢出 下述示例代码,由于递归深度没有限制且没有设置出口,每次方法的调用都会产生一个栈帧导致了创建的栈帧过多,而导致内存溢出(StackOverflowError)。 示例代码: 运行结果: 栈帧过大导致栈内存

理解java虚拟机内存收集

学习《深入理解Java虚拟机》时个人的理解笔记 1、为什么要去了解垃圾收集和内存回收技术? 当需要排查各种内存溢出、内存泄漏问题时,当垃圾收集成为系统达到更高并发量的瓶颈时,我们就必须对这些“自动化”的技术实施必要的监控和调节。 2、“哲学三问”内存收集 what?when?how? 那些内存需要回收?什么时候回收?如何回收? 这是一个整体的问题,确定了什么状态的内存可以

NGINX轻松管理10万长连接 --- 基于2GB内存的CentOS 6.5 x86-64

转自:http://blog.chinaunix.net/xmlrpc.php?r=blog/article&uid=190176&id=4234854 一 前言 当管理大量连接时,特别是只有少量活跃连接,NGINX有比较好的CPU和RAM利用率,如今是多终端保持在线的时代,更能让NGINX发挥这个优点。本文做一个简单测试,NGINX在一个普通PC虚拟机上维护100k的HTTP

PHP原理之内存管理中难懂的几个点

PHP的内存管理, 分为俩大部分, 第一部分是PHP自身的内存管理, 这部分主要的内容就是引用计数, 写时复制, 等等面向应用的层面的管理. 而第二部分就是今天我要介绍的, zend_alloc中描写的关于PHP自身的内存管理, 包括它是如何管理可用内存, 如何分配内存等. 另外, 为什么要写这个呢, 因为之前并没有任何资料来介绍PHP内存管理中使用的策略, 数据结构, 或者算法. 而在我们

string字符会调用new分配堆内存吗

gcc的string默认大小是32个字节,字符串小于等于15直接保存在栈上,超过之后才会使用new分配。

PHP内存泄漏问题解析

内存泄漏 内存泄漏指的是在程序运行过程中申请了内存,但是在使用完成后没有及时释放的现象, 对于普通运行时间较短的程序来说可能问题不会那么明显,但是对于长时间运行的程序, 比如Web服务器,后台进程等就比较明显了,随着系统运行占用的内存会持续上升, 可能会因为占用内存过高而崩溃,或被系统杀掉 PHP的内存泄漏 PHP属于高级语言,语言级别并没有内存的概念,在使用过程中完全不需要主动申请或释放内

C++学习笔记----6、内存管理(四)---- 通常的内存陷阱(2)

3、Windows环境下使用Visual C++发现并修复内存渗露         内存渗露很难跟踪是因为你无法很容易地看着内存并且看到什么对象处于使用中,一开始在哪儿分配的内存。然而,是有程序可以为你做到这一点的。内存渗露检测工具有昂贵的专业软件包,也有免费下载的工具。如果你是在Microsoft Visual C++环境下工作,它的排错工具库有内建的对于内存渗露检测的支持。该内存检测默认没有

控制台和MFC中内存泄露工具vld的使用

最近想检测下项目中内存泄露的情况,选中了vld这款。在查找使用方法的时候,大都是控制台下的示例,添加到main函数所在的源文件上。换成MFC就纠结了,不知道添加到哪里去。本文记录控制台和MFC中的使用vld过程。    vld资源:    1)、大家可以移步下边的网址下载:     http://vld.codeplex.com/releases/view/82311    2