14

Eu preciso saber se meu algoritmo atende a demanda do seguinte enunciado:

Implemente um algoritmo com complexidade O(n) que realize o fatorial de um número x tal que x pertence aos Naturais.

#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;
}

Se possível me expliquem como fazer a medição.

1

3 Respostas 3

13

A medição da complexidade de um algoritmo é tradicionalmente feita em ciências da computação utilizando-se análise assintótica a qual utiliza o que é chamado de notação Big O (o O(n) do qual seu enunciado fala).

Um algoritmo com complexidade O(n) é nada mais que um algoritmo de tempo linear, o que significa que o tempo que ele leva para executar é um reflexo direto do tamanho da entrada de dados que ele utiliza e que esse tempo cresce de forma constante e...linear!

Em termos práticos o desejado pelo enunciado do seu problema é que se digamos seu algoritmo realize uma etapa que leve aproximadamente 1 segundo para calcular a fatorial de 1 o cálculo da fatorial de 2 deveria realizar duas etapas e levar aproxidamente 2 segundos, a fatorial de 3 realizaria três etapas e levaria aproxidamente 3 segundos, e assim sucessivamente, para cada valor acima seu tempo cresce linearmente.

Quanto a seu algoritmo atender a demanda, sim ele atende, isso pode ser confirmado vendo que cada fatorial acima de um anterior gera apenas uma chamada extra a fatorial sendo que fatorial realiza apenas operações de tempo constante (não vou entrar em mais detalhes aqui pois o assunto é extenso, sugiro que veja os links que usei sobre análise assintótica e Big O).

7

A complexidade O(n) (linear) significa que para cada elemento da coleção que precisa manipular, deve haver no máximo um passo no algoritmo.

Você pode determinar a quantidade de passos fazendo um teste de mesa, ou seja, executar mentalmente o algoritmo e ir anotando as mudanças de estado das variáveis e sub-expressões, e ir contando os passos para atingir o objetivo.

Então por exemplo, se pedir o fatorial de 5 pode executar em até 5 passos. Para o fatorial de 8, pode fazer em até 8 passos.

Neste caso "passo" pode ser entendido a chamada à função fatorial.

Outra forma é ativar o debug e ir executando e vendo quantos passos ocorreram.

Mas o cálculo básico do fatorial é conhecido como sendo complexidade O(n) mesmo.

Coloquei no GitHub para referência futura.

2

A complexidade de algoritmos pode ser medida de diferentes modos, desde de intuitivamente para algoritmos fáceis, por exemplo, com laços de iteração, porém para algoritmos que envolvam recursão o método mais recomendo e formal, indico que pesquise sobre o Teorema Mestre, o qual envolvem três tipos de notação.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .