算法的例子和复杂度的直观图形
2018-07-01 本文已影响46人
夕阳下的不回头
这个题的隐含条件是
不仅集合T中的元素总和是m 且T的补集中的所有元素的和也是m
该题在生活中的现实例子
美国的选票制度是 先在一个区里看票数 如果在这个区里某候选人票数大于另外一个候选人的票数
那么在全国内的该区票数全归该候选人所有
比如加州就是55票全部加到该候选人头上
我们可以轻易看出只要候选人的选票多于270票
即可获胜
那么是否会出现一种情况使得两位候选人的票数均为269票？
这也就是我们刚才说的那个问题 抽象成数学模型就是
n=51 51个区 m=269 2m=538
那么给出
首先 直觉算法（最容易实现和想到的）：
上述问题是一个NPC问题
对于NPC问题 除非给出特定条件限制
否则上述的直觉算法已经是最好的了
直观理解:
在尺度很小的时候 一些时间复杂度并不能很好的体现出来
因此我们要增大尺度
