Notação Big-O

A notação Big-O é fundamental para a comparação de algoritmos distintos. Seu propósito é determinar a abordagem mais eficiente. Ao enfrentar um mesmo problema, frequentemente nos deparamos com diversas alternativas de solução. O Big-O nos proporciona um insight valioso sobre qual dessas abordagens pode se revelar a mais ágil.

Podemos afirmar sobre a notação Big-O:

• Como comparar dois ou mais algoritmos.
• Comparação objetiva entre algoritmos.
• Considera diferenças entre poder de processamento, sistema operacional, linguagem de programação
• O quanto a "complexidade" do algoritmo aumenta de acordo com as entradas.

Exemplos

Vamos supor que precisamos de uma função que some todos os números passados como parâmetros. Teremos duas pessoas desenvolvendo, o que resultará em duas soluções distintas. Nesse cenário, é crucial determinar qual abordagem se mostra mais eficaz.

Exemplo 1:

def soma1(n):
    total = 0
    for i in range(n + 1):
        total += i
    return total

time_taken = timeit.timeit(lambda: soma1(10))
print(f"Tempo levado: {time_taken:.6f} segundos")

# Tempo levado: 0.616551 segundos

A função soma1(n) realiza um loop que itera n + 1 vezes, onde n é o parâmetro passado para a função. Portanto, o número de passos que a função executa é proporcional a n.

Dizemos que a função soma1 tem uma complexidade de O(n), onde n representa a quantidade de passos e que o tempo de execução da função aumentará conforme o aumento do número de passos.

Exemplo 2:

def soma2(n):
    return (n * (n + 1)) / 2

time_taken2 = timeit.timeit(lambda: soma2(10))
print(f"Tempo levado: {time_taken2:.6f} segundos")

Tempo levado: 0.173197 segundos

A função soma2(n) utiliza uma fórmula matemática conhecida para calcular a soma dos números de 1 a n. (retorna a mesma coisa que a função anterior).

Dizemos que a função soma2 tem uma complexidade de O(3), onde 3 representa a quantidade de passos(Multiplicação, soma e divisão).

A função soma2 é uma abordagem mais eficiente para o caso, pois já tem uma quantidade definida de passos 'O(3)', afirmando que o quanto a "complexidade" do algoritmo aumenta de acordo com as entradas.

Conclusão

A notação Big-O é uma ótima abordagem para comparar dois ou mais algoritmos e desenvolver soluções mais rápidas e eficientes.