Regardless of whether you are a student or working as a programmer, and on what field you work, knowledge of algorithms and data structures necessary. These are important building blocks for solving problems.
Of course, you probably used a list or stack, but do you know how they work? If not, you can not be sure that the right decisions as to which algorithm to use.
Understanding the algorithms and data structures begins with the ability to determine and compare their complexity.
The asymptotic analysis
When we talk about measuring the complexity of algorithms, we mean the analysis of the time required for processing very large data sets. This analysis is called asymptotic. How long does it take to process an array of ten elements? Thousands? Ten million? If the algorithm to process thousands of items at five milliseconds, what happens if we give him a million? Will he run for five minutes or five years? Should not figure it out before the customer?
Everything is decided by small things!
The growth rate
The growth rate describes the complexity of the algorithm increases with the size of the input data. Most often, it is presented in the form of O-notation (from it. «Ordnung» - order): O (f (x)), where f (x) - a formula expressing the complexity of the algorithm. The formula may be present variable n, which represents the size of the input data. Below is a list of the most frequent orders growth, but it is by no means a complete.
A constant - O (1)
The growth rate of O (1) means that the computational complexity of the algorithm does not depend on the size of the input data. It should be remembered, however, that the unit in the formula does not mean that the algorithm is performed in a single operation or requires very little time. It may also require a microsecond, and year. It is important that this time is independent of the input data.
public int GetCount (int [] items)
{
return items.Length;
}
Linear - O (n)
The growth rate of O (n) means that the algorithm complexity increases linearly with the input array. If the linear algorithm processes one element of the five milliseconds, we can expect that it will process thousands of items in five seconds.
Such algorithms are easily recognized by the presence of the loop for each element of the input array.
public long GetSum (int [] items)
{
long sum = 0;
foreach (int i in items)
{
sum + = i;
}
return sum;
}
Logarithmic - O (log n)
The growth rate of O (log n) means that the running time grows logarithmically with the size of the input array. (Approx. .: Lane in the analysis of algorithms, the default logarithm to the base 2). Most of the algorithms operating on the principle of "halving" have logarithmic complexity. Contains method binary search tree (binary search tree) is also the order of growth O (log n).
Linearifmetichesky - O (n · log n)
Linearifmetichesky (linear or logarithmic) algorithm has order of growth O (n · log n). Some algorithms such as "divide and conquer" fall into this category. In the following sections we will see two such examples - merge sort and quick sort.
Quadratic - O (n 2)
Hours algorithm with order of growth O (n 2) is dependent on the square of the size of the input array. Despite the fact that such a situation can not be avoided sometimes quadratic complexity - a reason to reconsider the use algorithms or data structures. The problem is that they do not scale well. For example, if an array of thousands of items require
1 million operations, the array of elements need 1 million 000 000 000 000 operations. If any operation requires millisecond to perform a quadratic algorithm will handle millions of items for 32 years. Even if it is a hundred times faster, work takes 84 days.
We will see an example of an algorithm with quadratic complexity, when we study the bubble sort.
The best, medium and worst case
What do we mean when we say that the order of growth of the complexity of the algorithm - O (n)? This is the average case? Or the worst? Perhaps the best?
Usually it refers to the worst case, except in cases where the worst and the average are very different. For example, we see examples of algorithms which have an average rate of growth of the O (1), but occasionally may become O (n) (for example, ArrayList.add). In this case, we will indicate that the algorithm works in an average constant time, and explain the cases in which the difficulty increases.
The most important thing here is that the O (n) means that the algorithm requires no more than n steps.
What do we measure?
When measuring the complexity of algorithms and data structures, we usually talk about two things: the number of operations required to complete the work (computational complexity), and resources, in particular memory, which is required algorithm (spatial complexity).
The algorithm that runs ten times faster, but uses ten times more space may be quite suitable for the server machine with more memory. But in embedded systems where the amount of memory is limited, this algorithm can not be used.
In these articles, we will talk about the computational complexity, but when considering the sorting algorithms also touch on the issue of resources.
Operations, the number of which we measure include:
comparisons ("more", "less", "equal");
assignment;
memory allocation.
That is what we consider surgery usually clear from the context.
For example, in describing the search algorithm element in the data structure, we would almost certainly mean the comparison operation. Search - this is mainly the process of reading, so there is no point in doing an assignment or allocation.
When we talk about sorting, we can take into account both the comparison and the allocation and assignment. In such cases, we will clearly indicate what actions we are considering.
To be continued
This concludes our introduction to the analysis of the complexity of algorithms. Next time we will look at the first data structure - a linked list.
0 коммент.:
Post a Comment