计算机问题求解-算法在计算机科学中的地位课件.ppt

1、计算机问题求解计算机问题求解 论题论题1-141-14 -算法的效率算法的效率2018年12月18日需要移动多少次圆盘？n相应的递归方程是：T(n)=2T(n-1)+1即：T(n)=2n-1n当n=64(据说原始问题是这样的)：其数量级大约是 1019，即1000亿亿！如果每秒移动1亿个盘子，需要大约3200年！TSP:(也许是)世界上最具挑战性的（算法）问题。Rules that give a number of trials below the number of permutations of the given points are not known!这年头，我们当然使用计算机 n

2、假设我们使用 IBM Roadrunner Cluster(美国能源部）129,600个处理器，每秒执行1457万亿次算数运算 价值1亿3千3百万美元 2009年高性能计算机500强第一名n 解决33city-TSP耐心等待请勿关机We would then need roughly 28 trillion years to solve the 33-city TSP on the Roadrunner,an uncomfortable amount of time,given that the universe is estimated to be only 14 billion years

3、 old.问题 实例TSP TSP 挑战计算思维能力的极限一个例子 找序列中的最大元素如果我们关心A的值：显然：与实际输入有关；最小值：0；最大值：n-1;平均值：?“最坏情况”也不一定容易看出来n For any integer k1,if mn1 and n0By the way:The power of n grows more slowly than any exponential function with base greater than 1nk o(cn)for any c1顺便问一下：书上讲的优化方法如何实现？现在说说“平均”n假设要在n个元素的序列中搜索K；假设K确实在该序

4、列中的概率是q，则不在其中的概率是1-q。如果在其中，假设K出现在每一个位置上的概率是一样的。对于特定的位置i(0in-1),比较次数为i+1。因此，平均代价是：)1()1(10qninqni考你一下：考你一下：Let A be an array of integers and S a target integer.Design an efficient algorithm for determining if there exist a pair of indices i,j such that Ai+Aj=S.如果这里“efficient”是指“线性的”，你的答案满足要求吗？a1a2aiiHash(ai)ajIf ai=S-ajHash(S-aj)ASleeping TigersSleeping TigersConsideredcurrently课外作业nDH:pp.153-6.1 6.3 6.10,6.11 6.15,6.16