Computational complexity theory
From Simple English Wikipedia, the free encyclopedia
Computational complexity theory is a part of computer science. It looks at algorithms, and tries to say how many steps or how much memory a certain algorithm takes for a computer to do. Very often, algorithms that use fewer steps use more memory (or the other way round: if there is less memory available, it takes more steps to do). Unfortunately many interesting algorithms take a number of steps that is dependent on the size of the problem.
Contents |
[edit] Different classes of complexity
[edit] Linear complexity
Complexity theory also look at how a problem changes if it is done for more elements. Mowing the lawn can be thought of as a problem with linear complexity. Mowing an area that is double the size of the original takes twice as long.
[edit] Logarithmic complexity
This is generally different for problems that involve looking up things, like finding a word in a dictionary. If the dictionary is twice as big, it contains twice as many words as the original to compare to. Looking up something will take only one step more. The algorithm to do lookups is simple. The word in the middle of the dictionary will be either before or after the term than needs to be looked up, if the words do not match. If it is before, the term needs to be in the second half of the dictionary. If it is after the word, it needs to be in the first half. That way, the problem space is halved with every step, until the word or definition is found. This is generally known as logarithmic complexity
[edit] Exponential complexity
There are problems that grow very fast. One such problem is known as the Travelling salesman problem. A salesman needs to take a tour of a certain number of cities. Each city should only be visited once, the distance (or cost) of the travelling should be minimal, and the salesman should end up where he started. This problem has exponential complexity. There are n factorial possibilities to consider. Adding one city (from n to n+1) will multiply the number of possibilities by (n+1). Unfortunately, most of the interesting problems have this complexity.
