Como calcular o Fatorial de um número através de uma estratégia divisão e conquista?

Question

Escreva uma função recursiva que calcule o fatorial usando divisão e conquista como no algoritmo Merge-sort. Isso é, defina uma função fatorial(m,n) que calcule n x (n - 1) x ... m e chame essa função recursivamente para calcular o fatorial. Calcule também a complexidade desse algoritmo. Implemente na linguagem de sua preferência as versões força bruta (iterativa e recursiva) do problema e a versão divisão e conquista. Explique todos os detalhes de sua solução.

Answer 1

A linguagem escolhida foi Python 3.6..

Seguem abaixo as implementações do cálculo do fatorial nas versões força bruta - i) iterativa ii) recursiva - e iii) divisão e conquista, respectivamente:

i) Iterativa:

def factorial_it(n):
    f=1
    for i in range(1,n+1):
        f=f*i
    return f

ii) Recursiva:

def factorial_rec(n):
    if(n>1):
        return n * factorial_rec(n-1)
    else:
        return 1

iii) Agora, a partir da estratégia divisão e conquista:

Primeiro, importa-se o pacote math que adiante será utilizado para calcular um arrendondamento para baixo (floor). Logo depois, determina-se uma função que será responsável pelo cálculo do fatorial:

import math

def calc_fact(a,b):
    return a * b

Adiante, define-se uma função factorial(m,n), onde factorial(m,n)=n!/(m-1)!. Depois divide-se o problema em duas partes - elas são representadas pelas variáveis a e b. A variável a é definida como (m+p)!/(m-1)!, já a variável b é igual a n!/(m+p!), onde adotamos que p é a divisão inteira de (n-1) por 2 (ou seja, o ponto médio da nossa sequência, já que adotaremos nesse cálculo m=1). Em seguinte o problema é "fundido" (assim como no algoritmo Merge-Sort) em uma única variável c:

def factorial(m,n):
    c=m
    if(m!=n):
        p=math.floor((n-m)//2)
        a=factorial(m,m+p)
        b=factorial(m+p+1,n)
        c=calc_fact(a,b)
    return c

Agora, por exemplo, se o objetivo fosse calcular o fatorial de 4!, teríamos que (n=4, m=1) e factorial(1, 4) = factorial(1, 2) x factorial(2, 4), ou seja, dividiríamos o problema nos seguintes cálculos: 2!/0! e 4!/2!. O passo final seria fundir os sub-problemas chegando no resultado 2!/0! x 4!/2! = 4! (o equivalente a: (1 x 2) x (1 x 2 x 3 x 4)/(1 x 2) = 2 x 24/2 = 24.

Basta, então, imprimir a função factorial(1,n) - neste exemplo em particular factorial(1,4):

print(factorial(1,4))

24

Utilizando o Teorema Mestre calcula-se que a complexidade deste terceiro algoritmo é n log n. Nota-se que a assintoticamente este algoritmo é mais eficiente do que os dois primeiros, interação e recursão (os quais possuem complexidade equivalente a n). Observe que há uma economia de computação nesta estratégia, pois quanto maior for o cálculo do fatorial, mais multiplicações serão necessárias (e maior serão esses números). Então, dividindo o cálculo do nosso fatorial ao meio simplificamos de certa forma todas essas contas.

Answer 2

Felipe, boa implementação!

Uma alternativa é colocar a função calc_fat(a,b) dentro da outra função factorial(m,n). De modo que o código ficaria:

import math

def factorial(m,n):
    c=m
    if(m!=n):
        p=math.floor((n-m)//2)
        a=factorial(m,m+p)
        b=factorial(m+p+1,n)
        c=a*b                                                         # a função veio pra dentro da outra 
    return c

print(factorial(1,4))

24

O algoritmo ficaria um pouco mais curto e simples.