How to calculate the complexity of algorithms?

1

123qwe2015-09-25 16:37:10

Algorithms

123qwe, 2015-09-25 16:37:10

What's up, software.
Any topics that I see on algorithms are related to their analysis in one way or another.
I understood that algorithms from N log n type are the fastest, n ^ 2 are slower, and there seems to be just N and something.
What is it all about? This is somehow vaguely mentioned, and it is assumed that the reader knows these points.
Example
Suppose there is a number N that is equal to 1,000,000. How many times will an algorithm with an N log N exponent be faster than an algorithm with an N^2 exponent?
The answer is 50,000.
Why?

Reply

Answer the question

In order to leave comments, you need to log in

5 answer(s)

D

Denis Ineshin, 2015-09-25
@IonDen

Start with a series of articles on Habré Introduction to the analysis of the complexity of algorithms

P

protven, 2015-09-25
@protven

Suppose there is a number N that is equal to 1,000,000. How many times will an algorithm with an N log N exponent be faster than an algorithm with an N^2 exponent?
The answer is 50,000.
Why?
Because 1000,000 ^2 / (1000000 * log 1000000) ~ 50000
SUDDENLY!

S

smanioso, 2015-09-26
@smanioso

Start with a school math course.

R

Robert, 2015-09-28
@NgNl

It is impossible to determine the exact execution time of the algorithm using this notation; it gives an idea of the scale of complexity, and not of its exact value.
O(1) - time costs do not depend on the size of the task
O(log(n)) - if the task size is doubled, the time costs change by a constant value
O(n) - if the task size is doubled, the time costs will also increase two times
O(n^2) - if the task size is doubled, the time cost will increase by about four times
O(n*log(n)) - if the task is doubled, the time cost will double, plus some increase, the relative contribution of which decreases with increasing n. For small n, it can make a very large contribution. O(n*log(n)) starts growing like a square for small n, but then growth slows down to almost linear
O(n^p) - polynomial algorithms remain a dream for some problems.
O(a^n), O(n!), O(n^n) - non-polynomial algorithms, in order of increasing time cost

V

Vitaly Vitrenko, 2015-09-25
@Vestail

In this case, you don't even need to know the analysis of algorithms, just divide N^2/(NlogN) (base 2). In general, there are standard books like Kormen and company. From myself I can recommend Algorithms in Java "Robert Sedgwick, Kevin Wayne, very well explained and a lot of exercises.
There are also several courses on coursera 1 , 2 .