How to measure the complexity of an algorithm?

Question

How to measure the complexity of an algorithm?

Navigation

#1 by (8 votes)
#2 by (3 votes)
#3 by (1 votes)

7

Hello everyone. I need to know if my algorithm meets the demand of the following statement: "Implement an algorithm with complexity O (n) that realizes the factorial of a number x such that x belongs to the Natural."

#include <stdio.h>
/* recebe um inteiro x;
 * retorna o fatorial de x.
*/
int fatorial (int x)
{   
if (x == 0)
    return 1;
return x * fatorial(x-1);
}
int main (void)
{
int n;
scanf("%d", &n);
printf("%d\n", fatorial(n));

return 0;
}

If possible, explain how to do the measurement. Thanks in advance!

c

asked by anonymous 20.02.2016 / 17:57

3 answers

Do not open keyboard automatically when you enter screen with EditText Transform jQuery code into JavaScript

score 8 · Answer 1

Measuring the complexity of an algorithm is traditionally done in computer science using analysis asymptotic which uses what is called a notation # (the O (n) of which your utterance speaks).

An algorithm with complexity O (n) is nothing more than a linear time algorithm, which means that the time it takes to execute is a direct reflection of the size of the data input it uses and that this time grows steadily and ... linear!

In practical terms what is desired by the statement of your problem is that if we say your algorithm perform a step that takes approximately 1 second to calculate the factorial of 1 the calculation of the factorial of 2 should carry out two steps and take approximately 2 seconds, the factorial of 3 would perform three steps and would take approximately 3 seconds, and so on, for each value above its time grows linearly.

As for your algorithm to meet demand, yes it does, this can be confirmed by seeing that each factorial above an earlier one generates only an extra call to fatorial and fatorial only performs constant time operations (I'm not going To get into more detail here because the subject is extensive, I suggest you see the links I used on Asymptotic and Big O analysis.

score 3 · Answer 2

The complexity O (N) means that for every element of the collection that needs to be manipulated, there should be at most one step in the algorithm.

You can determine the number of steps by doing a table test, that is, by mentally executing the algorithm and annotating the state changes of the variables and sub-expressions, and by counting the steps to reach the goal. >

So for example if you ask for a factorial of 5, you can run it in up to 5 steps. For factorial of 8, you can do it in up to 8 steps.

In this case "step" can be understood to call the function fatorial .

Another way is to enable debug and run and see how many steps have taken.

But the basic factorial calculation is known to be O (N) complexity itself.

score 1 · Answer 3

The complexity of algorithms can be measured in different ways, from intuitively to easy algorithms, for example, with iteration loops, but for recursion algorithms the most recommend and formal method, it indicates that it searches on the Master Theorem, which involve three types of notation.