欢迎来到文档下载导航网!

3-5 易解性问题与难解性问题.pdf

时间:2021-01-06|当前位置:首页 > 教育文档 > 中学教育 > |用户下载:

3-5 易解性问题与难解性问题.pdf


本文档部分文本预览

Does complexity come from lengthy outputs? Our question is really this: Does such devastating time performance, requiring zillions of years of running time, show up only when the outputs are devastatingly lengthy? Can we find problems with short outputs that behave as badly? How about decision problems? An algorithm says only Yes Or No spends all of its time reachin a verdict. Can such problems be that bad too? Running times of various time complexity Assume that a computer is capable of a 1012 instructions per second: 10 50 100 200 2 -6 -9 -8 -8 N 10 2 10 10 4 10 second second second second N -9 -8 2 10 3 4 10 A 39 - digit no. second hours centres of centres NN 0.08 A 64 - digit no. A 179 - digit no. A 439 - digit no. second of centres of centres of centres Remark: The Big Bang was 12-15 billion years ago. Intractability An algorithm whose worst-time performance is captured by a polynomial function(such as log2 N, N,N2 and Nlog2 N)is called a good one. An algorithm that in worst case, requires super-polynomial time(such as 2N , N1 and NN)is a bad one. A problem that is solvable but admits only bad solutions is termed intractable. Tractability is robust Models of computations are polynomially related meaning that not only can a problem that is solvable in your model be solved in mine too. but the difference in running time will be polynomial. This is a refinement of the church-Turing thesis: not only is the class of computable problems robust, but so is the class of tractable problems. It is called Sequential computation thesis.

继续预览文档剩余内容

温馨提示:本页预览文本内容并非错乱,是从文档中提取部分无格式预览!如您需要正常预览文档全文,请点击下方按钮↓↓↓

上一篇:4.1 初次尝试——点和直线(上).pdf

栏    目:中学教育

下一篇:奋斗未来拼搏成就梦想演讲稿.doc

本文标题:3-5 易解性问题与难解性问题.pdf

本文地址:https://www.365weibook.com/html/20210106/635102.html

    正常预览或下载提示:

    本页面文档预览是由服务器自动提取的部分内容,并不是文档错乱。如您需要预览全文或下载文档,请点击页面左侧(点击去预览文档全文或下载文档)按钮,进行全文预览或下载。

推荐下载

联系我们 | 广告投放 |网站地图

免责申明:本网站不提供任何形式的下载服务,因此与之有关的知识产权纠纷本网站不承担任何责任。

如果侵犯了您的权利,请与我们联系,我们将进行删除处理。