[Algoritmos] Big O - Aula 1

Big O

A Big O Notation é uma forma de descrever o desempenho ou a complexidade de um algoritmo em termos do tempo de execução ou uso de memória, conforme o tamanho da entrada cresce. Ela ajuda a entender quão eficiente um algoritmo é ao lidar com grandes quantidades de dados.

Cenários

Omega (Ω) = O melhor cenário possível.

Theta (θ) = O cenário intermediário.

Big O (O) = O pior cenário possível.

O(n)

O O(n) significa que o tempo de execução do algoritmo cresce linearmente à medida que o tamanho da entrada (n) aumenta.

Se um algoritmo tem complexidade O(n), significa que, se você dobrar o tamanho da entrada, o tempo de execução também dobra.

Exemplo

Imagine que você tem uma lista de números e precisa encontrar um número específico dentro dela. O algoritmo pode simplesmente percorrer cada elemento até encontrar o número desejado.

Se a lista tiver 10 elementos, no pior caso (quando o número está no final ou não está na lista), o código faz 10 verificações. Se a lista tiver 1.000 elementos, faz 1.000 verificações. Esse crescimento linear mostra que a complexidade é O(n).

def encontrar_elemento(lista, alvo):
    for elemento in lista:  
        if elemento == alvo:
            return True  
    return False  

Drop Constants

No Big O Notation, ao analisar a complexidade de um algoritmo, desconsideramos constantes multiplicativas, pois elas não afetam o crescimento assintótico no longo prazo.

O objetivo do Big O é medir como o tempo de execução cresce conforme a entrada aumenta, e constantes não mudam a taxa de crescimento assintótica. Por exemplo:

• O(2n) SIMPLIFICAMOS PARA → O(n)
• O(100n) SIMPLIFICAMOS PARA → O(n)
• O(0.5n) SIMPLIFICAMOS PARA → O(n)

O(n^2)

O O(n^2) significa que o tempo de execução do algoritmo cresce proporcionalmente ao quadrado do tamanho da entrada (n).

Ele aparece geralmente em algoritmos que usam dois loops aninhados, onde cada loop percorre a entrada (n) vezes.

Exemplo

def exemplo(n):
    for i in range(n):
        for j in range(n):  
            print(i, j)  

Perceba que se (n) for 10, teremos 100 elementos printados, ou seja, 10 ^ 2 = 100.

Neste caso, temos um loop dentro de outro loop, ambos percorrendo (n) elementos. Isso resulta em n * n = n², então a complexidade final é O(n²).

Características do O(n²)

• Muito lento para entradas grandes.

• Aparece em loops aninhados.

• Pode ser otimizado para O(n log n) em alguns casos.

• Usado em algoritmos básicos como Bubble Sort ou Selection Sort.

Drop Non-Dominants

Significa ignorar os termos menos significativos de uma função de complexidade para focar apenas no termo que mais impacta o crescimento conforme a entrada (n) aumenta.

Quando analisamos a eficiência de um algoritmo, nos preocupamos principalmente com o comportamento de sua complexidade conforme (n) cresce. Os termos de menor ordem se tornam irrelevantes para grandes valores de (n), então podemos descartá-los.

Exemplo

def exemplo(n):
    for i in range(n):
        for j in range(n):      # O(n^2)
            print(i, j) 

	for k in range(n):          # O(n)
		print(k)

Na função teríamos:

O(n² + n) SIMPLIFICAMOS PARA → O(n²)

Para valores pequenos de (n), ambos os termos importam. Mas conforme (n) cresce, o termo n2n^2n2 cresce muito mais rápido do que (n). Então, descartamos (n) e simplificamos.

O(1)

O(1) significa tempo constante, ou seja, o tempo de execução do algoritmo não muda independentemente do tamanho da entrada.

Exemplo

def soma(n):
	return n + n

Nesse caso, independente do tamanho da soma, a operação ocorre em tempo constante O(1).

Casos comuns de O(1):

• Acessar um elemento de uma lista por índice: lista[i].

• Acessar um valor em um dicionário: dicionario[chave].

• Inserir um elemento em um set (conjunto), se não houver colisão.

O(log n)

O(log n) significa tempo logarítmico. Isso quer dizer que, conforme o tamanho da entrada (n) cresce, o tempo de execução cresce de forma muito mais lenta do que linearmente O(n).

Se um algoritmo tem complexidade O(log n), ele reduz a quantidade de trabalho necessária a cada passo. Isso geralmente acontece quando o problema pode ser dividido pela metade a cada iteração.

Exemplo

Binary Search:

# Vamos encontrar o 8

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 

5 - 6 - 7 - 8    #1

7 - 8      #2

8      #3

Obs: Não vou fazer o algoritmo para poupar tempo e espaço.

Perceba que em 3 passos o algoritmo é capaz de encontrar o número:

2 ^ 3 = 8

ou seja

log_2(8) = 3

Lists

[A - B - C - D]
 0 - 1 - 2 - 3

Devemos observar nas listas, que em caso de retirarmos o último item (D), ou se adicionarmos um item ao final da lista, isso irá resultar em um O(1), tendo em vista não ter que reindexar os valores.

No caso de adicionarmos ou removermos um item no meio ou no começo da lista, isso causará a necessidade de reindexar os itens da lista, o que resulta em O(n), sendo n o número de itens da lista.

Se quisermos buscar um item da lista:

Iterar sobre a lista = O(n)

Ir direto no index = O(1)