STL performance O (ln (n)) issues

Question

Please can someone explain this:

If the docs say that STL is std :: vector to find the element's speed performace = O (ln (n)), what does that mean.

O(ln(n)) - what is O ", where can I read about it?

And where can I read about the execution of other STL containers in the preliminary version

Thank you very much

Answer 1

The Big O sign is a way of measuring how the algorithm will scale as the size of the data it runs on increases.

Search for an element, if the vector is usually O(n) , it is only O(lg(n)) when the vector is sorted, and you use one of the binary search family of algorithms .

The complexity of each algorithm is indicated in the standard, as well as in any link (for example, the link to std::lower_bound ).

BTW, ln is an e based log , but all logarithms have the same complexity, therefore, although binary search only performs lg (log ₂ ) operations, it is technically correct to say O(ln(n)) .

Answer 2

This is known as the Big O designation, it is an expression of the asymptotic complexity of a given algorithm with respect to some parameters.

• asymptotics means that we are not interested in the first few cases, but about the behavior of the algorithm with increasing size of the input parameters.
• parameters depend on the measured algorithm
• operation in which we are interested

For example, in the case of a binary search, we express a relationship between the number of comparisons performed, depending on the size of the set in which we are looking.

Runtime can usually be inferred from this, but this is not always the case, especially if you have not chosen the right "operation" in terms of implementation or hardware limitations.

A few days ago, there was a good article on sorting using tape as storage. Since the difficulty in the search expresses the number of comparisons and the use of the tape as storage, the runtime mainly depends on the movement of the tape ... it turned out that the bubble system will work better than quicksort, despite the fact that in general it is described as slower.

Answer 3

The designation Big-O is the temporary complexity of program performance.

therefore, O (ln (n)) means that access to elements in std :: vector as the vector grows is proportional to ln (size_of_vector), but this is only with a sorted vector using binary search. Binary search is faster than linear, because you remove possible elements twice as fast, so ln is really base 2.

http://en.wikipedia.org/wiki/Big_O_notation

Answer 4

O is a note of big O. It describes the complexity of running an algorithm at runtime. In essence, this is the number of operations needed to compute a response.

Answer 5

All other answers were clarified by O to find the typical complexity of this algorithm on a decent link, for example this . At the bottom of each algorithm, the complexity of the algorithm is documented.

Answer 6

O - the abbreviation "Order". This is a measure of the time taken to complete the operation.

For example, this code is O (n ^ 2) because it will execute n * n times.

 int n = 100; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { } }