Analisando a complexidade de código com Python

A complexidade de um algoritmo é uma medida da quantidade de tempo e/ou espaço exigida por um algoritmo para uma entrada de determinado tamanho (n). Embora a complexidade do algoritmo dependa de fatores específicos como: arquitetura do computador (hardware), representação do Tipo Abstrato de Dados (TAD), eficiência do compilador, complexidade do algoritmo subjacente e tamanho da entrada. Entre esses, os fatores mais relevantes costumam ser a complexidade do algoritmo em si e o tamanho da entrada.

No blog da DataCamp, Python Data Structures Tutorial, você encontra uma visão geral das principais estruturas de dados e como implementá-las em Python. O artigo apresenta as estruturas de dados básicas da linguagem e aborda conceitos como Tipo Abstrato de Dados (TAD) e Estrutura de Dados, estruturas primitivas e não primitivas.

Análise assintótica

Análise assintótica é o cálculo do tempo de execução de um trecho de código ou de uma operação em termos matemáticos de computação. Suas operações são expressas em função de n, como f(n). Em análise matemática, a assíntota (assymptotics) é um método para descrever o comportamento no limite.

O tempo exigido por um algoritmo costuma ser analisado em três cenários: Pior caso – tempo máximo necessário e o mais usado na análise de algoritmos. Melhor caso – tempo mínimo necessário, raramente considerado sozinho. Caso médio – tempo médio para uma execução típica, às vezes utilizado na análise.

Notação assintótica

As notações mais usadas para calcular a complexidade de tempo de execução de um algoritmo são:

• Notação Big O
• Notação Big θ
• Notação Big Ω

Notação Big Oh, Ο

Big O mede o desempenho ou a complexidade de um algoritmo. Em termos matemáticos, é um limite superior para a taxa de crescimento de uma função: se uma função g(x) não cresce mais rápido que uma função f(x), então g pertence a O(f). Em geral, ela expressa o limite superior do tempo de um algoritmo, ou seja, a medida do pior caso — o maior tempo possível para concluir a execução.

Notação Big Omega, Ω

A notação Ω(n) é a forma formal de expressar o limite inferior do tempo de execução de um algoritmo. Ela mede o melhor caso — o menor tempo que o algoritmo pode levar para terminar.

Notação Big Theta, θ

A notação θ(n) expressa formalmente tanto o limite inferior quanto o limite superior do tempo de execução de um algoritmo.

Como cada notação é usada para estimar a complexidade

A notação Big O é a mais utilizada para encontrar o limite superior de um algoritmo. A notação Big θ é usada em alguns casos para descrever o caso médio e a notação Ω é a menos utilizada entre as três.

A seguir, você verá exemplos de como as notações são aplicadas para determinar a complexidade de um algoritmo específico.

Por exemplo, para o quicksort:

Quicksort é um algoritmo de divisão e conquista usado para ordenação. Ele organiza elementos em uma ordem (por exemplo, números em um array em ordem crescente ou decrescente). O algoritmo escolhe um pivô — um índice selecionado do array — e há diferentes estratégias para escolher esse pivô. No exemplo abaixo, o pivô é o último elemento.

O coração do quicksort é a partição. A partir do array, escolhe-se um elemento de partição; esse elemento (por exemplo, pit) é colocado na posição correta; os elementos maiores que o pivô ficam à direita e os menores, à esquerda.

#The last element will be taken as a pivot by the use of the function
#The smaller element is placed left to the pivot
#The greater element is placed to the right of the pivot
def partition(array,low,high):
    i = ( low-1 )         # index of smaller element is chosen
    pivot = array[high]     # pivot is chosen

    for j in range(low , high):

        #Is the element less or equal to the pivot
        if   array[j] <= pivot:

            # increment index of smaller element
            i = i+1
            array[i],array[j] = array[j],array[i]

    array[i+1],array[high] = array[high],array[i+1]
    return ( i+1 )

# The main crux of the problem that implements Quick sort is
#array[] is to be sorted
#high is the ending index
#low is the starting index

# Function to do Quick sort
def quickSort(array,low,high):
    if low < high:

       #pit is the partitioning index
        pit = partition(array,low,high)

      #Element sorted before and after partition
        quickSort(array, low, pit-1)
        quickSort(array, pit+1, high)

array=[2,4,6,8,10,12]
n = len(array)
quickSort(array,0,n-1)
print ("The Sorted array is:")
for i in range(n):
    print ("%d" %array[i]),

The Sorted array is:
2
4
6
8
10
12
Saída esperada:

The Sorted array is: 2 4 6 8 10 12

Agora é hora de analisar a complexidade de tempo. Primeiro:

• Melhor caso: Ω(n log n)
• Caso médio: Θ(n log n)
• Pior caso: O(n^2)

Vamos analisar o código acima.

Melhor caso: ocorre quando o elemento de partição escolhe um pivô aproximadamente no meio. Como o algoritmo chama recursivamente as metades, o total de passos é quantas vezes você divide n por 2 até chegar a 1: n / 2^k = 1. Como 2^{log n} = n, temos k = log n. Logo, o número de níveis é O(log n) e, como cada nível custa O(n), a complexidade fica O(n log n).

Caso médio: para o caso médio, é preciso considerar todas as permutações do array e calcular o tempo para cada uma. Você pode ler mais em Merge sort.

Pior caso: se o primeiro elemento (ou o último, em uma escolha ingênua) é sempre o pivô e a entrada já está em ordem crescente ou decrescente, após cada partição teremos tamanhos 1 e n-1. Seja T(n) o tempo para ordenar n elementos: T(n) = T(n-1) + O(n) => T(n) = O(n^2).

Exemplos

O código abaixo é simples — talvez você nem o chame de algoritmo — mas tecnicamente qualquer código que resolva algo é um algoritmo. O exemplo a seguir usa um laço for com um único print.

print('I love Python');

Hello world!
A complexidade de tempo do algoritmo acima é O(1), pois ele sempre executa um único passo — tempo constante.

stuffs= ['eggs','toothbrush','kittens','mugs']
for stuff in stuffs:
    print("Here's a stuff: {}".format(stuff));

Here's a stuff: eggs Here's a stuff: toothbrush Here's a stuff: kittens Here's a stuff: mugs Como você descreveria a eficiência do algoritmo acima na notação Big O?

Para analisar o algoritmo, considere quantos passos ele executa. No exemplo, há quatro itens na lista, e você imprime cada um. Mas e se houvesse 15 itens? O laço for levaria mais passos. Como ele executa tantos passos quanto o número de elementos, a eficiência é O(N), e não O(1).

O próximo exemplo é um algoritmo simples em Python para verificar se um número é primo:

def is_prime(number):   
    for i in range(2, number):       
        if number % 2 == 0:           
            return True   
    return False

O código acima recebe um número e inicia um laço for dividindo por todos os inteiros de 2 até esse número, verificando o resto. Se não houver resto, o número não é primo e a função retorna False imediatamente. Se você chegar até o fim sempre com resto, o número é primo e a função retorna True.

A eficiência desse algoritmo é O(N). Embora a entrada não seja uma lista, mas um único número, se você passar 11, o laço executa cerca de onze passos (na verdade, nove, pois começa em 2 e vai até antes do próprio número). Para 101, cerca de 101 passos. Como o número de passos cresce junto com o valor de entrada, é um exemplo clássico de O(N).

def twoForLoops(n):
    for i in range(1,n):
        print("Printing:"+i);
    for i in range(1,100):
        print("Printing:"+i);

No código acima, a complexidade é O(N). O segundo laço roda 100 iterações fixas, o que é irrelevante para N muito grande quando expressamos a ordem de crescimento.

def twoConditionalLoops(m,n):
    for i in range(0,m):
        print("Printing:"+i);
    for i in range(0,n):
        print("Printing:"+i);

Há dois laços: um de tamanho m e outro de tamanho n. Assumindo m e n grandes, a complexidade é O(n + m). Como os laços são independentes e recebem entradas diferentes, as complexidades se somam.

def twoNestedForLoops(int m,int n):
    for i in range(0,n):
        for j in range(0,m):
            print("Printing:"+(i*j));

Temos laços aninhados; assumindo n e m grandes, a complexidade é O(n*m). Como os laços são aninhados, as complexidades se multiplicam.

Parabéns!

Você chegou ao fim deste tutorial! Ao longo do caminho, aprendeu notação assintótica — uma ferramenta básica usada por programadores e cientistas de dados. Você viu uma forma simples e direta de analisar complexidade, em linguagem acessível e sem rigor matemático excessivo. Embora estruturas de dados e algoritmos sejam temas comuns em cursos de ciência da computação, é igualmente importante ter noções do assunto mesmo sem ser especialista. Para se aprofundar, confira: MIT OpenCourseWare — Algorithm course

Se quiser aprender mais sobre Python, explore estes cursos da DataCamp: