complexityComplexity is one of those terms for which it is difficult to give a precise definition. Intuitively, it is thought of as a property or feature that implies the opposite of simplicity. Complexity is often used to describe single sytems made of multiple interacting parts. However, complexity descriptions can be used for a large variety of applications.
Computational Complexity
A measure of the time and space requirments to perform a certain computational function.
Time Complexity
The length of time it takes to find a solution or complete a process.
Space Complexity
The amount of physical storage required for a system to perform a certain operation.
Kolmogorov (algorithmic) complexity - the length of the shortest program run on a universal Turing machine capable of performing a certain function or providing a certain output.
Connectivity Complexity
The number of relations/inter-connections betwen the components of a given system. The greater the extent of inter-connections between components of a system, the more difficult it is to decompose the system without changing its behaviour.
Descriptive/Interpretative Complexity
The complexity of a system which involves both a description (e.g. DNA) and a realization of the description (e.g. proteins in the cell). This complexity is measured as the total complexity of encoding the realisation into a descriptive code and decoding it back into a realisation of that code.
Functional Complexity
A sum of the complexity of the individual functions that can be realized by a single system.
Web Resources On complexity
http://bruce.edmonds.name/thesis/
http://www.iscid.org/boards/ubb-get_topic-f-6-t-000321.html
|
|
|
