今天要为大家介绍的是一种很“暴力”的算法,枚举。枚举除了很暴力外,它还是一种很常用、很好用的算法。枚举算法又名穷举算法。
枚举算法的思想是:将问题的所有可能的答案一一列举,然后根据条件判断此答案是否合适,保留合适的,丢弃不合适的。
想要使用枚举算法,首先要确定枚举对象、枚举范围和判定条件。
逐一枚举可能的解,验证每个解是否是问题的解,千万不要漏掉任何一个可能正确的解。
虽然枚举是一种很暴利的算法,但是仍可以通过缩小枚举范围来提高解决问题的效率。同时也要避免重复枚举。
看这样一道例题:
这道题要用枚举不错,枚举要每一位都用一个循环,这道题2个数,每个数5位,也就是说10位数,10个循环,每个循环从0循环到9,时间复杂度O(10^10)。
但这里给出了n的值,也就是说只要枚举一个数,另一个数可以求出来的。
a/b=c;
a/c=b.
所以我们仅需枚举一个数(5位)即可,时间复杂度一下就降至了O(10^5),他们之间可相差了不少呢,我们借助python来计算一下。
计算机运行次数减少了99亿多次!!!
可见通过缩小枚举范围来提高解决问题的效率有多重要。
关于枚举算法,就介绍到这里了。
领取专属 10元无门槛券
私享最新 技术干货