避免算法竞赛超时小技巧 |
您所在的位置:网站首页 › 如何缩短代码运行时间 › 避免算法竞赛超时小技巧 |
避免算法竞赛超时小技巧
虽然大家用的都是同样的思想,同样的算法,但是如果你在算法比赛在不注意这些小细节的话,将会大大的增加你程序的执行时间,增加甚至是将你算法程序的时间复杂度提升一个量级!
1. 在for循环的判断条件中使用求长度/大小的函数 很多小伙伴们在写for()循环的时候,喜欢在判断条件,但是这种方法看似让你省写了一个length变量,但是却让你的程序慢了许多。例如我们以下面两段程序为例: 第一段: int[] demo = new int[n]; int length = demo.length(); for (int i = 0; i 0 ? temp : 0;程序段的意思不变,但是执行想效率却要高了很多,尤其是在多次使用的时候。 3. 判断奇偶数的时候,使用’&'更高效 在判断一个数的奇数还是偶数的时候,很多小伙伴会使用%来求一个数除以2的余数来进行判断,其实这里我们有更高效的方法,那就是&与运算,如果a&1 == 1则a为奇数,a&1 == 0则a为偶数。 4. 能转换为迭代的函数,尽量不要写递归 5. 算法最高不要超过O(n^2) 在我们正常的算法竞赛中,当你写出来一个时间复杂度比O(n2)的算法时,那你这题基本是凉透了,或者说你只想拿前两个样例(如果是按测试点的比赛,如果实在想不出来,最后可以写个完全暴力,能骗几分是几分)。一般来说,时间效率到O(n 2)一般都很高了,已经很难过全部样例了,如果是压轴题的话,O(n)算法都比较难过全部样例,得需要优化到O(lgn)才保险。 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |