Content deleted Content added
m Put in separate heading for "Big Complexity" so it can be directly linked to from the "Time Complexity" page. |
→Resources: "Others" must at the end |
||
Line 12:
The usual units of time (seconds, minutes etc.) are not used in [[computational complexity theory|complexity theory]] because they are too dependent on the choice of a specific computer and on the evolution of technology. For instance, a computer today can execute an algorithm significantly faster than a computer from the 1960s; however, this is not an intrinsic feature of the algorithm but rather a consequence of technological advances in [[computer hardware]]. Complexity theory seeks to quantify the intrinsic time requirements of algorithms, that is, the basic time constraints an algorithm would place on ''any'' computer. This is achieved by counting the number of ''elementary operations'' that are executed during the computation. These operations are assumed to take constant time (that is, not affected by the size of the input) on a given machine, and are often called ''steps''.
{{anchor|bit complexity}}
Formally, the ''bit complexity'' refers to the number of operations on [[bit]]s that are needed for running an algorithm. With most [[models of computation]], it equals the time complexity up to a constant factor. On [[computer]]s, the number of operations on [[machine word]]s that are needed is also proportional to the bit complexity. So, the ''time complexity'' and the ''bit complexity'' are equivalent for realistic models of computation▼
===Space===
Line 21 ⟶ 25:
{{anchor|bit complexity}}
For many algorithms the size of the integers that are used during a computation is not bounded, and it is not realistic to consider that arithmetic operations take a constant time. Therefore, the time complexity, generally called '''bit complexity''' in this context, may be much larger than the arithmetic complexity. For example, the arithmetic complexity of the computation of the [[determinant]] of a {{math|''n''×''n''}} [[integer matrix]] is <math>O(n^3)</math> for the usual algorithms ([[Gaussian elimination]]). The bit complexity of the same algorithms is [[exponential function|exponential]] in {{mvar|n}}, because the size of the coefficients may grow exponentially during the computation. On the other hand, if these algorithms are coupled with [[modular arithmetic|multi-modular arithmetic]], the bit complexity may be reduced to {{math|[[soft O notation|''O''<sup>~</sup>(''n''<sup>4</sup>)]]}}.
▲===Bit Complexity===
▲Formally, the ''bit complexity'' refers to the number of operations on [[bit]]s that are needed for running an algorithm. With most [[models of computation]], it equals the time complexity up to a constant factor. On [[computer]]s, the number of operations on [[machine word]]s that are needed is also proportional to the bit complexity. So, the ''time complexity'' and the ''bit complexity'' are equivalent for realistic models of computation
In [[sorting]] and [[search algorithm|searching]], the resource that is generally considered is the number of entries comparisons. This is generally a good measure of the time complexity if data are suitably organized.
| |||