计算复杂性(一).pptxVIP

计算复杂性（一）;你是某大公司的骨干，经常得到大老板的赏识。 某天大老板给你个简单的问题，很快你就给出了答案。 不久，大老板给你同样的问题，只不过这次数据变大了，你满怀信心的说“So easy!”。 一小时过去了，一天过去了，一个月过去了，一年过去了……结果……？？？; 给定一个数集A，问是否可以将其分成两个不相交的子集，使得两个子集中的元素之和相等？ 若所有元素之和为奇数，则显然不行。但是，元素之和为偶数呢？ {1,3,6,8} 1+8=3+6=9 {2,7,15,28,34,48,56,77,106,113} 2+7+15+106+113=28+34+48+56+77=243;{1,5,9,16,18,23,28,29,35,37,39,41,45,48,49,55,56, 67,68,69,72,75,78,79,81,86,88,95,100,106,112,115, 118,122,125,127,135,138,140,145,149,155,162,168, 177,178,180,195,199,201,205,209,215,220,224,228, 229,233,238,239,245,248} 1+5+……+168+177=178+180+……+245+248=3686;枚举法（穷举法）;旅行售货商问题The Traveling Salesman Problem;若干定义;定义3：对于一个优化问题，如果给定任意一个实例，算法总能找到一个可行解，那么就称之为近似算法；如果进一步这个可行解的目标值总等于最优值，则称之为最优算法. 问：是否任何数学问题都有算法求解呢？ 答案是否定的. 停机问题：是否存在一个算法，对于任意给定的图灵机都能判定任意的初始格局是否会导致停机？ 著名英国数学家图灵（Turing）证明了不存在一个算法，它能对该问题的一切实例给出正确答案.;定义4：算法时间复杂性是关于实例输入长度的函数，用来表示算法的时间需求.对于每一个可能的输入长度，它是该算法解此输入长度的最坏可能的实例所需的时间（基本运算步数）。 定义5：若存在一个常数 ，使得对所有 ，都有 ，则称函数 是 .时间复杂性是 的算法称为多项式时间算法.不能这样限制时间复杂性函数的算法称为指数时间算法.;;;;定义6：一个优化问题如果已经找到了多项式时间算法，那么就称它为多项式时间可解问题.把所有这样的问题集合记为P，因此多项式时间可解问题就称为P类问题. 定义7：答案为“是”或“否”的问题称为判定问题. 问：优化问题与其相应的判定问题的困难程度是否相当？;定义8：给定一???判定问题，如果存在一个算法，对任何一个答案为“是”的实例，该算法首先给出一个猜想，该猜想规模不超过实例输入长度的某个多项式函数，且验证猜想的正确性仅需多项式时间，那么称该问题属于NP类. 定理1：如果问题 ，那么存在一个多项式 使得 能用时间复杂性为 的确定型算法求解.;七大数学难题