Computationally Expensive Algorithm

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).

• Context:
  • It can (typically) be for an Intractable Computational Task.
  • It can be classified according to a complexity measure such as polynomial time measure.
  • …
• Example(s):
  • a Computationally Expensive Multi-objective Optimization Algorithm such as:
    • an unoptimized algorithm involving black box functions.
    • computational fluid dynamics simulations utilizing finite element algorithms.
  • …
• Counter-Example(s):
  • an Inefficient Algorithm, whose task time performance is significantly higher than the theoretically optimal of the task.
  • a Computationally Inexpensive Algorithm,
  • an Heuristic Algorithm.
  • a Memory Intensive Algorithm.
  • a Swarm Intelligence Algorithm,
  • a Tabu Search Algorithm,
  • a Simulated Annealing Algorithm,
  • a Genetic Algorithm,
  • Artificial Neural Networks,
  • Support Vector Machines.
• See: Computational Complexity Theory, Exponential Algorithm, NP-hard, Cost Model, Multi-objective Optimization Problem, Evolutionary Algorithm, Pareto Optimal Front.

---

---

References

2019

• (Chugh et al., 2019) ⇒ Tinkle Chugh, Karthik Sindhya, Jussi Hakanen, and Kaisa Miettinen (2019). "A Survey On Handling Computationally Expensive Multiobjective Optimization Problems with Evolutionary Algorithms". In: Soft Computing, 23(9), 3137-3166. DOI:10.1007/s00500-017-2965-0.
  • QUOTE: In many problems, explicit formulations of objective or constraint functions are not known and such functions are called black box functions. Usually, problems involving such functions need a long time to be solved e.g. problems involving computational fluid dynamics simulations utilizing finite element algorithms take substantial time to obtain one solution. These are examples of problems that we refer to as computationally expensive multiobjective optimization problems.

2009

• (Wikipedia, 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.

2003

• (Hromkovic, 2003) ⇒ Juraj Hromkovic (2003). "Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography". In: Springer Science & Business Media.
  • QUOTE: Thus, we conjecture, for many of these problems, that there does not exist any algorithm solving them within polynomial time of the input size, but we are unable to prove that one really needs more than $O(n)$ time to solve them. Missing a sufficiently powerful mathematical machinery to prove lower bounds on complexity makes classifying problems with respect to their hardness really difficult.

---