江苏龙网

  1. 首页 > 生活 > >

怎样估算算法的复杂度

评测机的话：OJ和正式的比赛一定会写明评测机各参数的，如果只是想比较准确的知道实际评测的效率，可以搞一些无聊的大递归交上去试试（比如1e8次求mod），最多不过几个TLE/WA而已。好在大家的机器基本上差不多，除非碰到恶意卡常数的情况，否则凭借一般人的常识足够了（比如1e4^2脸没洗好不要试，几e6的规模nlgn多半能赌一下常数和数据放水，1e8线性算法交之前看好自己的常数，再大就想想sqrt和log）。自己代码的话：有个好方法：随便来个极限数据，拿自己的机器跑一下（如果你觉得自己的机器太快，可以将自机的0.5s当成1s）。如果数据不好构造，算法复杂度一眼看不出怎么办？（我感觉下面这部分全是跑题）一个完整的题目可能由好几个步骤构成，我们分类来看一下各种小的情况~DP： DP的分析一般比较简单，状态和转移都是自己设计的，复杂度基本没什么悬念，如果你用了复杂的结构来搞各种优化，多想想平摊分析一般还是没什么压力的。图结构、数据结构： 这类题经典模板用的比较多，将几层经典算法组合在一起也很常见，分析有压力的话（一般不会）加起来就好了，平摊分析有时候也很给力的。贪心： 贪心能够超时可不多见……如果你使用了某些复杂的估价方法，一步步分析吧（哦有些时候也许可以平摊）。网络流（这个单独说）： 网络流超时一般只有三种情况：你建图建傻了 or 这个模型的一些特性使得它可以被优化成其他算法 or 你写错了不要去考虑什么O(V^2E)，那是每次都考虑很差情况分析出来的。一般来说比赛中分析网络流的复杂度毫无意义……字符串： 嗯……C/C++的各种函数速度还是不错的，常数没有有些时候我们相信的那样可怕。一般来说，匹配算法等等经典模板分析不动直接记住就可以了，复杂的串处理一般都是卡编码时间而不是执行时间。（如果真的遇到了需要分析的情况，说不定平摊分析还可以救命）模拟： ……好像没什么值得说的，复杂的模拟一般还是卡编码时间而不是执行时间。数学： 无论是组合、数论、还是数位统计你多半的思考时间是在压缩和合并各种信息上面。看看你要处理的信息和输入是什么关系，你能合并多少信息。搜索：在我心中赛场上能把启发搜索分析清楚的都是大神。疯狂剪枝不一定有好效果（数据可能是特殊的），搜索题很少见的，多交交……
■网友
谢邀。算法的空间复杂度比较好估计。对于时间复杂度，可以估计语句执行次数与输入问题规模之间的关系。例如一层循环就是线性复杂度，二分算法就是对数复杂度。详细的复杂度估计方法可以参阅维基百科。一般竞赛评测用计算机1秒接受的时间复杂度约为 【怎样估算算法的复杂度】 怎样估算算法的复杂度
条语句。
■网友
一般是1e8 但是区域赛可以接近1e9

■网友
正常情况凭经验咯比如1e9的O（N）谁都知道过不了但是不正常的情况（比如青岛某题50W的数据n2能A就没办法咯_§:з)))」∠)_


    推荐阅读


    上一篇：爱卡汽车|软件问题解决 第八代高尔夫已恢复交付

    下一篇：「User experience」在中国大陆是不是普遍缩写作「UE」?