剪枝思想及其妙用

剪枝一词源自树木修剪的行为，在此指代的是去除多余的部分以达到调整结构的目的。具体而言，则是通过修剪掉多余的部分来调整树冠结构或更新现有枝叶等。在算法领域中，则是通过避免冗余的操作与搜索来优化过程。其核心理念在于或是从结果中去除冗余的部分从而提高效率。

这里举三个不同类型算法的例子，以更好的理解剪枝思想的应用：

质数

• 剪枝一： 基于质数定义的方法是检查从2到n-1之间的所有整数是否有能整除n的情况；另一种更为高效的方式则是通过检查从2到√n之间的所有整数是否有能整除n的情况。前者的时间复杂度为O(n)，而后者的时间复杂度则为O(√n)。

• 剪枝操作中：原本设定为从数值2开始一直到n-1进行检查筛选的范围被优化为仅需检查至平方根值n

  • 剪枝二： 在确定了数值2符合条件后，在后续的筛选过程中只需关注大于等于3且小于等于平方根值n的所有奇数值即可完全替代原本需要考虑所有数值的情况；这样一来不仅能够显著降低计算量还能将时间复杂度降低至约原来的一半即O(sqrt(n)/2)

• 剪枝操作：基于区间[2, √n]进行筛选，在此范围内仅考虑奇数值。

  • 剪枝三：观察一个关于质数分布的重要规律——不小于5的所有质素都必定与6的倍数值相邻（如5与7、11与13等）。需要注意的是这类情况并非普遍现象（如35这样的情况）。

证明：令x≥