文档状态：编辑....

• 今日音乐
  

有点厌倦.

背景

分治法固然很棒,但是多叉的分裂可以很容易看出随着问题的规模变大,时间复杂度会走向指数级的爆炸,所以我们应该想尽办法将问题降为多项式级的复杂度,从几何角度我们应该尽力将树剪枝.动态规划即从剪枝的思想触发,减去重复的枝以降低复杂度.
分治法的确是解决问题的好办法,但是认清问题的目标是很重要的,分治法并不是用来优化解题速度的,它只是一种解决问题的方案,当我胡乱思考的时候,我开始考虑一些没用的东西,比如分治法加在规模n上与加在规模n/2的消耗时间不是线性的2倍,其实这种想法似乎毫无意义看一下一些分治法的时间复杂度公式比如T(n)=T(n/2)+O(n),我以前纵使将目光放在T(n)与T(n/2)这种递归的展开中,然后到最后对大量的分支难以控制,其实我的关注点出现了错误,我应该将目光投向O(n)上面,T(n)与T(n/2)提供的树的深度,O(n)提供了每一层的复杂度,两者相乘得到最终的复杂度

清奇脑回路

此处略微谈一下贪心算法,贪心算法的特性请自行熟悉一下,我准备简单的说一下对它使用的认识,暂时说不清这是什么角度,感觉很奇妙又很混乱,众所周知,我们是在寻求最优解,此时借用一下背包问题,里面涉及到重量和价值的权衡(二元),单位质量内寻求最大价值,如下图(注意点是离散的)所示,x轴表示价值,y轴标识重量,设斜率为K,只有此曲线是指数形式时(即K呈增长趋势),才能表示能够使用贪心算法.
说明:

从x轴任取取一点x'>0,其值为f(x'),对于任意x1>0,x2>0,x1+x2=x',存在f(x1)+f(x2)<f(x')

图像是离散的,代表子问题最小的切割规模.

[索引]分治法考虑两个问题,怎样分,如何治,分决定了了树的高度,轻微影响了治的复杂度和策略.而治的策略决定了治的复杂度.分的策略决定了整体问题的解决思路,体现了子问题具有的特性,

[分治法与减治法]
问题背景:
钢条切割问题和f(n)=n*f(n-1)
思考思路:
入口考虑的是解与问题规模的关系,如果不同规模的问题对解的影响不能进行线性叠加(此时脑中引入二叉树),就不能够乱用分治法,比如:....,当然我说的是不能乱用,而不是不能用,因为即使不能线性叠加,但是子问题规模对解的影响可能服从一定的规律,例如:y=x^2,y=3x^2[x是规模,y是影响度],倘若是简单的数学性规律叠加也罢,但是问题总是不会呈现简单规律的,当影响度与问题规模呈现非相关性关系时,那么我们在使用分治法时就出现了最优问题,我们要选用哪一种规模作为最优规模进行分割,所以枚举是少不了的,但是这种枚举会在代码级别影响编写代码的简洁性(有可能不影响),但是当采用了减治法,我们可以通过for循环进行迭代式操作.