Information about Algorithmic Efficiency
In computer science, efficiency is used to describe several desirable properties of an algorithm or other construct, besides clean design, functionality, etc. Efficiency is generally contained in two properties: speed (the time it takes for an operation to complete), and space (the memory or non-volatile storage used up by the construct). Optimization is the process of making code as efficient as possible, sometimes focusing on space at the cost of speed, or vice versa.
The speed of an algorithm is measured in various ways. The most common method uses time complexity to determine the Big-O of an algorithm: often, it is possible to make an algorithm faster at the expense of space. This is the case whenever you cache the result of an expensive calculation rather than recalculating it on demand. This is a very common method of improving speed, so much so that languages often add special features to support it, such as C++'s mutable keyword.
The space of an algorithm is actually two separate but related things. The first part is the space taken up by the compiled executable on disk (or equivalent, depending on the hardware and language) by the algorithm. This can often be reduced by preferring run-time decision making mechanisms (such as virtual functions and run-time type information) over certain compile-time decision making mechanisms (such as macro substitution and templates). This, however, comes at the cost of speed.
The other part of algorithm space measurement is the amount of temporary memory taken up during processing. For example, pre-caching results, as mentioned earlier, improves speed at the cost of this attribute.
Optimization of algorithms frequently depends on the properties of the machine the algorithm will be executed on. For example, one might optimize code for time efficiency in applications for home computers with sizable amounts of memory, while code to be placed in small, memory-tight devices may have to be made to run slower to conserve space.
One simple way to determine whether an optimization is worthwhile is as follows: Let the original time and space requirements (generally in Big-O notation) of the algorithm be
and 
. Let the new code require 
and 
time and space respectively. If 
, the optimization should be carried out. However, as mentioned above, this may not always be true.
One must be careful, in the pursuit of good coding style, not to over-emphasize efficiency. Nearly all of the time, a clean and usable design is much more important than a fast, small design. There are exceptions to this rule (such as embedded systems, where space is tight, and processing power minimal) but these are rarer than one might expect.
A macro in computer science is a rule or pattern that specifies how a certain input sequence (often a sequence of characters) should be mapped to an output sequence (also often a sequence of characters) according
..... Click the link for more information.
The speed of an algorithm is measured in various ways. The most common method uses time complexity to determine the Big-O of an algorithm: often, it is possible to make an algorithm faster at the expense of space. This is the case whenever you cache the result of an expensive calculation rather than recalculating it on demand. This is a very common method of improving speed, so much so that languages often add special features to support it, such as C++'s mutable keyword.
The space of an algorithm is actually two separate but related things. The first part is the space taken up by the compiled executable on disk (or equivalent, depending on the hardware and language) by the algorithm. This can often be reduced by preferring run-time decision making mechanisms (such as virtual functions and run-time type information) over certain compile-time decision making mechanisms (such as macro substitution and templates). This, however, comes at the cost of speed.
The other part of algorithm space measurement is the amount of temporary memory taken up during processing. For example, pre-caching results, as mentioned earlier, improves speed at the cost of this attribute.
Optimization of algorithms frequently depends on the properties of the machine the algorithm will be executed on. For example, one might optimize code for time efficiency in applications for home computers with sizable amounts of memory, while code to be placed in small, memory-tight devices may have to be made to run slower to conserve space.
One simple way to determine whether an optimization is worthwhile is as follows: Let the original time and space requirements (generally in Big-O notation) of the algorithm be
and . Let the new code require and time and space respectively. If , the optimization should be carried out. However, as mentioned above, this may not always be true.
One must be careful, in the pursuit of good coding style, not to over-emphasize efficiency. Nearly all of the time, a clean and usable design is much more important than a fast, small design. There are exceptions to this rule (such as embedded systems, where space is tight, and processing power minimal) but these are rarer than one might expect.
See also
Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems.
..... Click the link for more information.
..... Click the link for more information.
In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will proceed through a well-defined series of successive states, eventually terminating in an
..... Click the link for more information.
..... Click the link for more information.
In computing, optimization is the process of modifying a system to make some aspect of it work more efficiently or use fewer resources. For instance, a computer program may be optimized so that it executes more rapidly, or is capable of operating within a reduced amount of memory
..... Click the link for more information.
..... Click the link for more information.
As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e.g.
..... Click the link for more information.
..... Click the link for more information.
C++
Paradigm: Multi-paradigm
Appeared in: 1983
Designed by: Bjarne Stroustrup
Typing discipline: Static, unsafe, nominative
Major implementations: G++, Microsoft Visual C++, Borland C++ Builder
Dialects: ISO/IEC C++ 1998, ISO/IEC C++ 2003
..... Click the link for more information.
Paradigm: Multi-paradigm
Appeared in: 1983
Designed by: Bjarne Stroustrup
Typing discipline: Static, unsafe, nominative
Major implementations: G++, Microsoft Visual C++, Borland C++ Builder
Dialects: ISO/IEC C++ 1998, ISO/IEC C++ 2003
..... Click the link for more information.
In object-oriented programming (OOP), a virtual function or virtual method is a function whose behavior, by virtue of being declared "virtual," is determined by the definition of a function with the same signature furthest in the inheritance lineage of the instantiated
..... Click the link for more information.
..... Click the link for more information.
In programming, RTTI (Runtime Type Information, or Runtime Type Identification) means keeping information about an object's data type in memory at runtime. Run-time type information can apply to simple data types, such as integers and characters, or to generic objects.
..... Click the link for more information.
..... Click the link for more information.
- ''For other uses, see Macro (disambiguation)
A macro in computer science is a rule or pattern that specifies how a certain input sequence (often a sequence of characters) should be mapped to an output sequence (also often a sequence of characters) according
..... Click the link for more information.
In computer programming, templates are a feature of the C++ programming language that allow code to be written without consideration of the data type with which it will eventually be used. Templates support generic programming in C++.
..... Click the link for more information.
..... Click the link for more information.
An embedded system is a special-purpose computer system designed to perform one or a few dedicated functions.[1] It is usually embedded as part of a complete device including hardware and mechanical parts.
..... Click the link for more information.
..... Click the link for more information.
Memory locality (or data locality) is a term in computer science used to denote the temporal or spatial proximity of memory access in computer programs. There are two basic types of locality of memory reference: temporal and spatial:
..... Click the link for more information.
- Temporal locality
..... Click the link for more information.
As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e.g.
..... Click the link for more information.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
