Copy a string in constant time?

I've seen the operation of copying a string describ开发者_如何学JAVAed as O(n), where n is the length of the string, because it's assumed that we need to iterate through each character of the string and copy it individually. However, is it not possible for a compiler to generate instructions that can copy an entire block of memory in constant time? Does such a capability even exist on today's common architectures?

Not as far as I know.

However, for O() notation to be meaningful, you have to define the cost of each basic operation first. This is often omitted, because "it's obvious". And most of the time it really is. Your (hypothetical) scenario is a good example of a situation where defining the costs is essential.

Another, slightly more useful example is in the analysis of disk or tape storage search/sort algorithms.

If you use an instruction that copies an arbitrarily large block of data, then that single instruction is bound to take O(n) time itself.

Some CPU architectures had a single instruction to copy a block of memory form one location to another, but that single instruction took many cycle, so it was still O(n). No matter what, the CPU will have to read each character via the address bus, so there is no way to get around O(n).

1. I think you mean constant time, or less than linear, because O(n) is linear.

2. It is not possible, because of how memory works. When you copy something something has to access every cell of the memory and copy it to a different cell. It is possible to make something that will several cells in parallel, but not a variable number of cells. In the end every bit has to be copied using an electrical wire, and you have to assume that your memory is larger than the qty of wires that connect the system. It doesn't necessarily have to consume computational time, since you have independent elements like DMI, that can free up processor time, and let you compute other stuff in parallel.

P.S. Your question mixes theoretical computer science, with real world technology and implementation, so it was hard to answer in the spirit of the question, but I've tried to address the points you've raised.

In .NET strings are immutable reference objects. They are "copied" in constant time because only the reference needs to be copied.