ACM中的CPU和memory怎么降低?用C++语言

来源:百度知道 编辑:UC知道 时间:2024/07/07 21:30:47
ACM编程的题目我能做一些,但是cpu和memory的值就是降不下来,谁帮忙解释一下,最好举一些算法对比的例子。(我用C++的)

ACM 的题目, 如果你的时间 和内存不够的话, 估计你的算法不对, 或者你必须对数据进行压缩处理(不过这种情况在动态规划中,常见)
ACM, 里面的题目一般的,如果有一个正确的思路,他的TIME (你说的 cpu , 就是指运行时间吧,有的是称cpu, 不过都一样),和 MEMORY 都是很充裕的~~

比如说: acm.pku.edu.cn 上的 1088 题目(滑雪).
初一看, 很想直接搜索 , 就能搞定.. 但是当你写出,一提交,给的结果是"Time Limit Exceed"! . 而且,不管你怎么再对这搜索进行剪支都无法 Accepted .
这为什么一直会超时呢? 这主要是: 在直接搜索里面,有很多重复的操作.对于这种有重复操作的情况很容易想到”动态规划”. 动态规划实现有基本两种方法,一个是由开始状态递推到结果,另外一个是所谓的”记忆搜索”(对于复杂的递推关系,一般用’记忆搜索’较容易实现).
这个题目用,’记忆搜索’就可以了. 它只需要在原来的搜索的基础稍做改动就可以.定义一个数组,保存一下当前结果. 当下次在搜索到这儿时,就不用再往下搜索,直接从数组取出信息即可,从而达到加速的效果.

你可以发现,算法上做了一个小的改进后,提交时间就变为 0S.如果你在只从 空间 和 时间上做分析,可以发现, 它是用内存(多定义一个数组)来换取时间 ..

因此,在写程序的时候,我们得考虑: 空间 和 时间 做一下平衡.

建议你看这本书:
Computer System-A Programer Perspective

比较厚,但讲的很深入