Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como medir empiricamente a complexidade computacional de um código em Python?

+1 voto
161 visitas

2 Respostas

+2 votos
respondida Abr 2, 2016 por Caue (226 pontos)  
editado Abr 15, 2016 por Caue

Fiz uma alteração no código (executado com Python 3.5.1) para comparar mais duas implementações da sequência de Fibonacci:

import time
import numpy as np
import matplotlib.pyplot as plt
import functools


def fibonacci_smart_recursive(n, x1=0, x2=1):
    return x1 if (n == 1) else fibonacci_smart_recursive(n-1, x2, x1+x2)


def fibonacci_loop(n, x1=0, x2=1):
    a, b = x1, x2
    for _n in range(2, n+1):
       a, b = b, a+b
    return a


def fibonacci_recursive(n, x1=0, x2=1):
    if n == 1:
        return x1
    elif n == 2:
        return x2
    else:
        return fibonacci_recursive(n-1, x1, x2) + fibonacci_recursive(n-2, x1, x2)


@functools.lru_cache()
def fibonacci_recursive_lru_cache(n, x1=0, x2=1):
    if n == 1:
        return x1
    elif n == 2:
        return x2
    else:
        return fibonacci_recursive_lru_cache(n - 1, x1, x2) + fibonacci_recursive_lru_cache(n - 2, x1, x2)


if __name__ == '__main__':

    implementations = (fibonacci_smart_recursive, fibonacci_loop, fibonacci_recursive_lru_cache, fibonacci_recursive)

    n = 12
    theTimes = np.empty([n, len(implementations)])
    theN = np.empty([n])
    step = 2
    N = -step+1

    for i in range(0, n):
        N += step
        theN[i] = N

        for (index, f) in enumerate(implementations):
            beg_ts = time.time()
            f(N)
            end_ts = time.time()
            theTimes[i, index] = end_ts-beg_ts

    ax = plt.subplot(111)

    for (index, f) in enumerate(implementations):
        ax.plot(theN, theTimes[:, index]*1000, label=f.__name__, linewidth=2)

    ax.set_ylabel('Execution Time (ms)')
    ax.set_xlabel('n')
    ax.legend(loc='upper center', fancybox=True, shadow=True)
    plt.savefig('thetimes.eps')
    plt.show()

Resultados:

A imagem será apresentada aqui.
A imagem será apresentada aqui.

Editado:

Comparação com o algoritmo que usa matriz:

def fibonacci_matrix(n):
    matrix = np.array([[0, 1], [1, 1]], dtype=object)
    return np.linalg.matrix_power(matrix, n)[0][0]

A imagem será apresentada aqui.

comentou Abr 3, 2016 por danielcajueiro (5,251 pontos)  
Que legal esse @functools.lru_cache()! Não conhecia esse decorador! Parece que ele faz algo tipo uma memorização usualmente feita usando dicionários. É impressionante que o tempo gasto é praticamente constante!
+1 voto
respondida Abr 2, 2016 por danielcajueiro (5,251 pontos)  

Veja o exemplo abaixo comparando dois códigos para o cálculo da sequência de Fibonacci:

import time
import numpy as np
import matplotlib.pyplot as plt


def fibonacci_smart_recursive(n,x1,x2):
    if(n==1):
        return x1
    else:
        if(n==2):
            return x2
        else:
            return fibonacci_smart_recursive(n-1,x2,x1+x2)

def fibonacci(n):
    fm2=0
    fm1=1
    if(n>2):
        for i in range(2,n):
            f=fm1+fm2
            fm2=fm1
            fm1=f
        return f               
    else:
        if(n==2):
            return 1    
        else:
            return 0 



if __name__ == '__main__':

    n=10
    theTimes=np.empty([n,2])
    theN=np.empty([n])
    step=50
    N=-step+1

    for i in range(0,n):
        N=N+step
        theN[i]=N
        print i

        beg_ts = time.time()    
        fibonacci(N)
        end_ts = time.time()
        theTimes[i,0]=end_ts-beg_ts

        beg_ts = time.time()    
        fibonacci_smart_recursive(N,0,1)
        end_ts = time.time()
        theTimes[i,1]=end_ts-beg_ts    

    ax = plt.subplot(111)
    ax.plot(theN,theTimes[:,0],color='b')
    ax.plot(theN,theTimes[:,1],color='r')    
    ax.set_ylabel('Execution Time')
    ax.set_xlabel('n')    
    plt.show()

    plt.savefig('thetimes.eps')   

Esse código gera a seguinte figura:

A imagem será apresentada aqui.

...