Computationally Expensive Algorithm

From GM-RKB
Jump to: navigation, search

A Computationally Expensive Algorithm is an algorithm with high computational complexity (that requires a large number of steps to complete relative to its task input size).



References

2009

  • http://en.wikipedia.org/wiki/Computationally_expensive
    • A computationally expensive algorithm is one that, for a given input size, requires a relatively large number of steps to complete; in other words, one with high computational complexity. The "cost" of an algorithm relative to the size of its input is often represented using Big O notation.
    • For some expensive algorithms, there are less expensive counterparts. A traditional example in which multiple algorithms exist to achieve the same end is the class of sorting algorithms used to order a one-dimensional list. From the point of view of implementation, the so-called bubble sort is one of the simplest of these algorithms. It is, however, relatively computationally expensive, requiring more computation steps for a list of given size than almost any other standard algorithm. As such, bubble sort is virtually never used in practice. For real-life sorting problems, much more efficient algorithms are used, such as Quicksort; these, however, are somewhat more complicated in their implementation.
    • Often, the more general an algorithm, the more computationally expensive it is. For example, algorithms used for manipulating a generic matrix will work on a sparse matrix, but algorithms designed specifically for sparse matrices will be less expensive.