Content deleted Content added
m →Abstract machine: source added |
m source added |
||
Line 18:
To analyze an algorithm precisely, one must assume it is being executed by a particular [[abstract machine]]. For example, on a [[random access machine]], [[binary search algorithm|binary search]] can be used to rapidly locate a particular value in a sorted list in only O(log ''n'') comparisons, where ''n'' is the number of elements in the list; on a [[Turing machine]], this is not possible, since it can only move one memory cell at a time and so requires Ω(''n'') steps to even reach an arbitrary value in the list.
Moreover, different abstract machines define different ''primitive'' operations, which are operations that can be performed in constant time. Some machines, like Turing machines, only permit one bit at a time to be read or written; these are called bit operations, and the number of bit operations required to solve a problem is called its '''bit complexity'''<ref>{{Cite web|title=On the bit complexity of finding points in connected components of a smooth real hypersurface {{!}} Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation|url=https://dl.acm.org/doi/abs/10.1145/3373207.3404058|access-date=2020-07-29|website=dl.acm.org|language=EN|doi=10.1145/3373207.3404058}}</ref>. Bit complexity generalizes to any machine where the memory cells are of a fixed size that does not depend on the input; for this reason, algorithms that manipulate numbers much larger than the registers on ordinary PCs are typically analyzed in terms of their bit complexity. Put another way, the bit complexity is the complexity when the word size is a single bit, where word size is the size of each memory cell and register.<ref>{{Cite journal|last=ElliottJesse|last2=SchostÉric|date=2019-12-17|title=Bit complexity for critical point computation in smooth and compact real hypersurfaces|url=https://dl.acm.org/doi/abs/10.1145/3377006.3377014|journal=ACM Communications in Computer Algebra|language=EN|doi=10.1145/
Another commonly used model has words with log ''n'' bits, where ''n'' is a variable depending on the input. For example, in [[graph algorithm]]s, it is typical to assume that the vertices are numbered 1 through ''n'' and that each memory cell can hold any of these values, so that they can refer to any vertex. This is justified in problems where the input uses Ω(''n'') words of storage, since on real computers, the memory cell and register size is typically selected in order to be able to index any word in memory. Operations on these words, such as copies and arithmetic operations, are assumed to operate in constant time, rather than O(log ''n'') time. The number of word operations required to solve a problem in this model is sometimes called its '''word complexity'''.
| |||