Computational overhead

Computational overhead

In computer science, overhead is generally considered any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to be utilized or expended to enable a particular goal. It is a special case of engineering overhead.For example, an algorithm which caches frequent results for quick retrieval has the overhead of maintaining the memory to store the cached results. In terms of Algorithmic efficiency, overhead is often the terms which are asymptotically irrelevant.

Example

Consider two algorithms based on input length "n": algorithm "A", which takes n^2 operations, and algorithm "B", which takes 4n+7 operations. On short inputs such as n=5 or less, algorithm "A" is more efficient. Algorithm "B" is said to have overhead which constitutes the 4 extra operations for each input length and 7 additional operations (overhead may be used to describe all or any part of the additional operations). However, when the input is large, say n=6 or more, algorithm "B" is much more efficient. Overhead may also be used to decide whether or not to include features in software engineering. If developing for an embedded system, a feature that has a high memory overhead may not be included.

ee also

Algorithmic efficiency


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Computational — may refer to: Computer Computational algebra Computational Aeroacoustics Computational and Information Systems Laboratory Computational and Systems Neuroscience Computational archaeology Computational auditory scene analysis Computational biology …   Wikipedia

  • Overhead — may be: Overhead (business), the ongoing operating costs of running a business Engineering overhead, ancillary design features required by a component of a device Computational overhead, ancillary computation required by an algorithm or program… …   Wikipedia

  • Overhead crane — An overhead crane, featuring runways, bridge, and hoist in a traditional industrial environment …   Wikipedia

  • Bin (computational geometry) — In computational geometry, the bin data structure allows efficient region queries, i.e., if there are some axis aligned rectangles on a 2D plane, answer the question Given a query rectangle, return all rectangles intersecting it . kd tree is… …   Wikipedia

  • DomainKeys Identified Mail — (DKIM) is a method for associating a domain name to an email message, thereby allowing a person, role, or organization to claim some responsibility for the message. The association is set up by means of a digital signature which can be validated… …   Wikipedia

  • Airmass — For air mass in meteorology, see air mass .In astronomy, airmass is the optical path length through Earth s atmosphere for light from a celestial source.As it passes through the atmosphere, light isattenuated by scattering and absorption; the… …   Wikipedia

  • Houdini (software) — This article is about a high end 3D animation software. For chess engine, see Houdini (chess). Houdini is a high end 3D animation package developed by Side Effects Software which is headquartered in Toronto, Canada. Its chief distinction from… …   Wikipedia

  • ANT (network) — ANT is a proprietary wireless sensor network technology featuring a wireless communications protocol stack that enables semiconductor radios operating in the 2.4GHz Industrial, Scientific and Medical allocation of the RF spectrum ( ISM band ) to… …   Wikipedia

  • Simplex noise — is a method for constructing an n dimensional noise function comparable to Perlin noise ( classic noise) but with a lower computational overhead, especially in larger dimensions. Ken Perlin designed the algorithm in 2001 [Ken Perlin, Noise… …   Wikipedia

  • Magic (software) — This article is about the VLSI tool. For the Rapid application development tool, see Magic Software Enterprises. Magic Original author(s) John Ousterhout Initial release 1980s Stable release 7.5 / May 31, 2009; 2 years ago&# …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”