8 time complexities that every programmer should know Computer Science |
| 8 time complexities that every programmer should know Posted: 08 May 2018 06:31 AM PDT | ||||||||||||||||||
| Formal definition of time complexity using Turing machines? Posted: 08 May 2018 10:42 AM PDT Hi. So I've been reading Michael Sipser's intro to theoretical CS just for fun so I have no professional qualifications. But I've understood how basic automatas and the Turing machine work and the difference between recognisers and deciders and how computational problems can be reframed as the task of determining if a language is recognisable or decidable. And I also have a basic understanding of big-O notation and how given a high-level description of an algorithm we can determine the time complexity. But how is time complexity defined formally using Turing machines? A computable function is a function for which there exists a Turing machine such that when the input string is written on the tape at the start, the machine will halt leaving the output on the tape. Time could be measured in terms of the number of changes in state of the Turing machine it takes from start to halt. So I can imagine each computable function would have a table as follows: Example taken is the look-and-say value of a number.
So I've designed a Turing machine that satisfies the task. I've also designed it such that it takes an unusually large number of steps for processing the input 42. How do we determine whether the Turing machine functions in O(n) or O(n^2) or O(2^n)? Is n the length of the input or the output or some combination of both? It is possible that the machine took more steps simply because the input or output is unusually large. (It is possible for small inputs to have unusually large expected outputs or large inputs to expect small outputs) It is also possible that for different inputs of the same length the machine make take vastly different numbers of steps to reach the output (even if the output is small in length). P.S. I'm asking primarily because I want to understand the P versus NP problem. [link] [comments]  |
| You are subscribed to email updates from Computer Science: Theory and Application. To stop receiving these emails, you may unsubscribe now. | Email delivery powered by Google |
| Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States | |
No comments:
Post a Comment