Content deleted Content added
m Added {{unreferenced}} tag to article using Friendly |
|||
Line 1:
{{orphan|date=February 2010}}
{{unreferenced|date=January 2010}}
In [[computational complexity theory]] and [[analysis of algorithms]], a number of metrics are defined describing the resources, such as time or space, that a machine needs to solve a particular problem. Interpreting these metrics meaningfully requires context, and this context is frequently implicit and depends on the field and the problem under consideration. This article describes a number of important pieces of context and how they affect metrics.
Line 31 ⟶ 33:
Because disk operations are orders of magnitude slower than accesses to main memory, the typical metric used in disk-based algorithms is the number of disk seeks or the number of blocks read from the disk, which depend on both the input and the parameters of the disk. RAM accesses and CPU operations are "free." Similarly, in many models used to study data structures, such as the [[Cache-oblivious algorithm|cache-oblivious model]], operations on cached data are considered "free" because they are typically orders of magnitude faster in practice than access to main memory. Consequently, the typical metric used is the number of cache misses, which depends on both the input and parameters of the cache.
[[Category:Computational complexity theory]]
| |||