I saw a RAM model diagram that displayed an input tape, output tape, the program (read-only), the instruction pointer, and the memory registers. However, when I look at questions of time complexity, it is relevant how much time the program needs to spend on one action. Say you want to read one integer symbol from the read tape, add it to an integer from a memory register, and then squish the result into the write tape cell, and then move the read head one to the right and the write head one to the left. How much time or how many moves did I just waste?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ It doesn't matter along as these operations take constant time, since we're always interested only in the asymptotic complexity. $\endgroup$– Yuval FilmusSep 15, 2012 at 9:14
-
2$\begingroup$ I don't fully agree with Yuval. We are not always interested only in asymptotics, but the RAM model is certainly geared towards it; all operations are assumed to be equally expensive. You can beef up the model to be as close to reality as possible, making analyses harder at the same time. $\endgroup$– RaphaelSep 15, 2012 at 13:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Complexity is usually defined using Turing machine model to avoid the issue of the amount of resources taken during a complicated operation like adding integers.
You can use different notation of complexity of a RAM machine and that depends on what you are trying to do. If you want to be able to compare it with standard complexity classes which are defined using Turing machines then you should assign to each operation an amount of resource usage that a Turing machine would require to simulate that operation. The answer also depends on what kind of operations your RAM machine supports.
The standard RAM model consists of a finite control where a program is stored, one or more accumulator registers $Acc$, an instruction counter, and an infinite collection of memory registers $R[0], R[1],\ldots$. The instruction can be divided to four categories:
flow-control: unconditional jump, Accept, Reject, Halt, conditional jumps (the "conditions" are simple like $Acc = 0?$);
input/output: read, write;
- data-transfer between accumulator and memory: load, save;
- arithmetic: $Acc := 0$, add $R[i]$ to $Acc$;
Two more common costs are uniform and logarithmic. The two are related quadraticaly for the instruction set above (i.e. to convert the uniform to logarithmic you need to square the running time). Logarithmic means taking cost to be logarithm (i.e. the number of bits) of the inputs to the operation whereas uniform means that all operations are considered to take unit time.
