Linear-Time Algorithm: Difference between revisions
Jump to navigation
Jump to search
m (Text replacement - ". " to ". ") |
m (Text replacement - "]]↵↵----↵" to "]]. ---- ") |
||
| Line 17: | Line 17: | ||
** Informally spoken, the [[running time]] increases linearly with the size of the input. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list. This description is slightly inaccurate, since the running time can significantly deviate from a precise proportionality, especially for small values of ''n''. For more information, see the article on [[big O notation]]. | ** Informally spoken, the [[running time]] increases linearly with the size of the input. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list. This description is slightly inaccurate, since the running time can significantly deviate from a precise proportionality, especially for small values of ''n''. For more information, see the article on [[big O notation]]. | ||
** Linear time is often viewed as a desirable attribute for an algorithm. Much research has been invested into creating algorithms exhibiting (nearly) linear time or better. This research includes both [[software]] and [[hardware method]]s. In the case of hardware, some algorithms which, mathematically speaking, can never achieve [[Linear-Time Algorithm|linear time]] with standard [[computation model]]s are able to run in [[Linear-Time Algorithm|linear time]]. There are several hardware technologies which exploit [[parallelism]] to provide this. An example is [[content-addressable memory]]. | ** Linear time is often viewed as a desirable attribute for an algorithm. Much research has been invested into creating algorithms exhibiting (nearly) linear time or better. This research includes both [[software]] and [[hardware method]]s. In the case of hardware, some algorithms which, mathematically speaking, can never achieve [[Linear-Time Algorithm|linear time]] with standard [[computation model]]s are able to run in [[Linear-Time Algorithm|linear time]]. There are several hardware technologies which exploit [[parallelism]] to provide this. An example is [[content-addressable memory]]. | ||
** This concept of Linear Time is used in string matching Algorithms such as [[Boyer–Moore string search algorithm|Boyer-Moore Algorithm]], [[Ukkonen's Algorithm]] | ** This concept of Linear Time is used in string matching Algorithms such as [[Boyer–Moore string search algorithm|Boyer-Moore Algorithm]], [[Ukkonen's Algorithm]]. | ||
---- | ---- | ||
Latest revision as of 03:50, 8 May 2024
A Linear-Time Algorithm is an algorithm with Linear-Time Complexity Running Time.
- …
- Counter-Example(s):
- See: Computational Complexity Analysis Task.
References
2009
- http://en.wikipedia.org/wiki/Linear_time
- In computational complexity theory, an algorithm is said to take linear time, or O(n) time, if the asymptotic upper bound for the time it requires is proportional to the size of the input, which is usually denoted n.
- Informally spoken, the running time increases linearly with the size of the input. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list. This description is slightly inaccurate, since the running time can significantly deviate from a precise proportionality, especially for small values of n. For more information, see the article on big O notation.
- Linear time is often viewed as a desirable attribute for an algorithm. Much research has been invested into creating algorithms exhibiting (nearly) linear time or better. This research includes both software and hardware methods. In the case of hardware, some algorithms which, mathematically speaking, can never achieve linear time with standard computation models are able to run in linear time. There are several hardware technologies which exploit parallelism to provide this. An example is content-addressable memory.
- This concept of Linear Time is used in string matching Algorithms such as Boyer-Moore Algorithm, Ukkonen's Algorithm.