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.
- 01-062020——2021学年高中人教版（2019）化学选择性必修第一册 第一