4 ms·
So, is there such a thing as a useful O(1)-space algorithm? I can't think of a single one.
by jmpeax 13y ago
So, is there such a thing as a useful O(1)-space algorithm? I can't think of a single one.
- repsilat 13y ago(Particular, individual) regular expressions can be implemented with O(1) space. Regular expressions can do lots of useful things.
- jmpeax 13y agoThis is incorrect, under deliriums pedantic interpretation of space complexity. Some regular expressions require one to accept a certain number of examples of a character. This means that storage space for the count is required, which scales logarithmically in the count.
- repsilat 13y agoThis is why my comment began with the words "particular, individual". A regex like (1{5}0{3})\* can be implemented in constant space, but a language like matches(n, m, string): return matches((1{n}0{m})\*, string) cannot. Just think about it -- the former is just a DFA, and so of course you can do it in constant space (provided your input stream is abstracted away, or you use a TM.
- JackpotDen 13y agoint x = 0; x++; would be two examples.
- jmpeax 13y agoHow many times would you need to execute line 2? The more times you need to do this, the more values x needs to be able to represent. So running x++ in O(n) time means the space needed to store the accumulation grows as O(n log_2 n)... under delirium's "pedantic" interpretation of space complexity. Unknowingly you have allowed me to stumble onto an actual algorithm with O(1) storage pace, that is, one where there are n numbers, and you want to calculated the modulo-k sum. In this case, the algorithm scales logarithmically in the constant parameter k, but O(1) in n.