Como avaliar a complexidade de um algoritmo ou…

Para avaliar a complexidade de um algoritmo, utiliza-se a análise assintótica, que permite descrever a eficiência do algoritmo em função do tamanho dos dados de entrada ($n$). Os passos principais:

Definição de operações básicas: Identificam-se as operações cujo tempo de execução depende significativamente de $n$ (por exemplo, comparações, atribuições, operações aritméticas).
Cálculo do número de operações: Determina-se a quantidade de operações básicas em função de $n$. Isto pode ser uma fórmula exata ou uma estimativa.
Determinação da classe assintótica: Utilizam-se as notações Grande O ($O$), Omega ($\Omega$) e Theta ($\Theta$) para descrever o comportamento assintótico superior, inferior e exato, respetivamente.
- $O(f(n))$: O algoritmo executa-se em tempo que não excede uma constante multiplicada por $f(n)$ para grandes $n$. É usado para descrever o pior caso.
- $\Omega(f(n))$: O algoritmo executa-se em tempo que não é inferior a uma constante multiplicada por $f(n)$ para grandes $n$. É usado para descrever o melhor caso.
- $\Theta(f(n))$: O algoritmo executa-se em tempo proporcional a $f(n)$ para grandes $n$. É usado para descrever o caso médio ou quando o melhor e pior caso têm a mesma ordem assintótica.

O uso mais frequente é a Grande O ($O$) para descrever o limite superior do tempo de execução, o que é importante para compreender a escalabilidade do algoritmo no pior cenário.

Omissão de constantes e termos menores: Ao determinar a notação assintótica, ignoram-se os fatores constantes e os termos de menor ordem, pois para grandes $n$ domina a função com o maior expoente. Por exemplo, para $3n^2 + 5n + 10$, a notação assintótica será $O(n^2)$.

Classes assintóticas típicas (por ordem crescente de complexidade):

$O(1)$: Complexidade constante (tempo de execução não depende de $n$).
$O(\log n)$: Complexidade logarítmica (tempo de execução cresce muito lentamente com o aumento de $n$, característico de algoritmos de busca binária).
$O(n)$: Complexidade linear (tempo de execução é proporcional a $n$, característico de buscas lineares simples).
$O(n \log n)$: Complexidade linear-logarítmica (típico de algoritmos de ordenação eficientes como Quick Sort ou Merge Sort).
$O(n^2)$: Complexidade quadrática (tempo de execução cresce com o quadrado de $n$, típico de algoritmos de ordenação simples como Bubble Sort).
$O(n^c)$ (para $c > 1$): Complexidade polinómica.
$O(c^n)$ (para $c > 1$): Complexidade exponencial (tempo de execução cresce muito rapidamente com $n$, típico de buscas exaustivas).
$O(n!)$: Complexidade fatorial (a mais elevada classe de complexidade, cresce de forma extremamente rápida).

Para determinar a assintótica de estruturas cíclicas:

Blocos de código sequenciais: Soma-se a complexidade dos blocos. $O(A+B) = O(\max(A, B))$.
Laços aninhados: Multiplica-se o número de iterações dos laços. Um laço com $n$ iterações dentro de outro com $m$ iterações tem complexidade $O(n \times m)$. Se $m=n$, então $O(n^2)$.
Laços com redução do tamanho da entrada: Por exemplo, dividir por 2 a cada iteração leva a uma complexidade logarítmica ($O(\log n)$).

Exemplo:

Percurso simples de um array:

# Recontagem de operações básicas (comparações, atribuições)
# A operação principal é a comparação no ciclo
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 atribuição (fora do ciclo)
    for i in range(1, len(arr)): # O ciclo é executado len(arr) - 1 vezes
        # Dentro do ciclo:
        # 1 comparação (if arr[i] > max_val)
        # potencialmente 1 atribuição (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Se o tamanho do array for $n = \texttt{len(arr)}$, o ciclo é executado $n-1$ vezes. Em cada iteração, realiza-se um número constante de operações. O número total de operações é proporcional a $n$. Complexidade assintótica: $O(n)$.

Exemplo: Ordenação por inserção (Insertion Sort)

# Recontagem de operações básicas
# Operações principais: comparações e atribuições/deslocamentos de elementos
def insertion_sort(arr):
    # O ciclo externo é executado em $n-1$ vezes
    for i in range(1, len(arr)):
        key = arr[i] # 1 atribuição
        j = i - 1 # 1 atribuição
        # O ciclo interno no pior caso é executado $i$ vezes
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 atribuição (deslocamento)
            j -= 1 # 1 subtração e 1 atribuição
        arr[j + 1] = key # 1 atribuição

O ciclo externo é executado $n-1$ vezes. No pior caso (array em ordem inversa), o ciclo interno executa em média $i$ vezes (ou até $i$ vezes). A soma das operações em todas as iterações do ciclo externo é aproximadamente $1 + 2 + ... + (n-1) \approx n^2/2$. Complexidade assintótica: $O(n^2)$ no pior e médio caso, $O(n)$ no melhor caso (array já ordenado). Ao avaliar a complexidade, geralmente considera-se o pior caso (Grande $O$).

Como avaliar a complexidade de um algoritmo ou determinar a sua assimptota?