Complexidade de Tempo - Big (O)
A notação Big O (O) é usada para descrever a complexidade de tempo de um algoritmo e expressa o crescimento do tempo de execução à medida que o tamanho dos dados de entrada aumenta. Ela fornece uma maneira de comparar e classificar a eficiência relativa de diferentes algoritmos.
A notação Big O fornece uma estimativa superior do tempo de execução, indicando o pior caso possível para o desempenho do algoritmo. Ela se concentra nos fatores dominantes que afetam o tempo de execução, ignorando detalhes menores e constantes multiplicativas.
Por exemplo, O(n) indica um tempo de execução linear, onde o tempo aumenta proporcionalmente ao tamanho dos dados de entrada. O(n^2) indica um tempo de execução quadrático, onde o tempo aumenta quadrativamente com o tamanho dos dados.
A notação Big O não fornece uma medição precisa do tempo real de execução de um algoritmo, mas oferece uma estimativa útil para comparar a eficiência relativa entre diferentes algoritmos e identificar como o tempo de execução aumenta com base no tamanho dos dados. Algoritmos com uma complexidade de tempo menor (por exemplo, O(1) ou O(log n)) são geralmente considerados mais eficientes do que aqueles com complexidades de tempo maiores (por exemplo, O(n) ou O(n^2)).
Notações de complexidade de tempo na análise de algoritmos.
Tempo constante O(1): O tempo de execução é independente dos dados de entrada. Não importa o tamanho dos dados, o tempo de execução permanece constante.
Tempo linear O(n): O tempo de execução aumenta linearmente com o tamanho dos dados de entrada. Para cada elemento adicional nos dados, o tempo de execução aumenta proporcionalmente.
Tempo logarítmico O(log n): O tempo de execução reduz o tamanho dos dados de entrada a cada iteração, geralmente pela metade. Isso ocorre porque o algoritmo divide repetidamente os dados para encontrar a solução.
Tempo quadrático O(n^2): O tempo de execução aumenta quadraticamente com o tamanho dos dados de entrada. Isso ocorre quando há um loop aninhado, onde cada iteração do loop externo executa o loop interno.
Tempo exponencial O(2^n): O tempo de execução dobra para cada elemento adicional nos dados de entrada. Esse tipo de complexidade é comum em algoritmos de força bruta, onde todas as combinações possíveis são testadas.
Tempo fatorial O(n!): O tempo de execução cresce de forma fatorial com o tamanho dos dados de entrada. É a forma mais extrema de complexidade de tempo e é geralmente impraticável para valores grandes de n.
Algoritmos com complexidades exponenciais e fatoriais são ineficientes para tamanhos de entrada maiores e geralmente não são viáveis. Portanto, é importante projetar algoritmos eficientes que tenham complexidades de tempo mais baixas, como O(1), O(log n) ou O(n), sempre que possível.
Exemplos de código para ilustrar cada uma das complexidades de tempo mencionadas:
Tempo constante O(1):
def constant(n):
result = n * n
return result
Neste exemplo, independentemente do valor de n, o tempo de execução é constante. O algoritmo realiza uma única operação de multiplicação, sem depender do tamanho dos dados de entrada.
Tempo linear O(n):
def linear(n, A):
for i in range(n):
if A[i] == 0:
return 0
return 1
Neste caso, o tempo de execução aumenta linearmente com o tamanho do array A. Para cada elemento no array, o algoritmo verifica se é igual a zero. O número de iterações é diretamente proporcional ao tamanho do array.
Tempo logarítmico O(log n):
def logarithmic(n):
result = 0
while n > 1:
n //= 2
result += 1
return result
Neste exemplo, o tempo de execução diminui à medida que o valor de n é dividido pela metade em cada iteração. O algoritmo conta quantas vezes é possível dividir n por 2 até que n seja menor ou igual a 1.
Tempo quadrático O(n^2):
def quadratic(n):
result = 0
for i in range(n):
for j in range(i, n):
result += 1
return result
Neste caso, há dois loops aninhados. Para cada iteração do loop externo, o loop interno é executado, aumentando quadrativamente o número total de iterações. O tempo de execução é diretamente proporcional ao quadrado do valor de n.
Tempo exponencial O(2^n):
def exponential(n):
if n <= 0:
return
elif n == 1:
print("Hello")
else:
exponential(n - 1)
exponential(n - 1)
Neste exemplo recursivo, o algoritmo chama a função duas vezes com um valor reduzido em 1 a cada chamada. Isso resulta em uma árvore de chamadas recursivas exponencialmente crescente. O tempo de execução aumenta exponencialmente à medida que n aumenta.
Tempo fatorial O(n!):
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
Neste exemplo recursivo, o algoritmo calcula o fatorial de um número n. Cada chamada recursiva é feita com um valor reduzido em 1, resultando em um número crescente de chamadas recursivas. O tempo de execução aumenta de forma fatorial à medida que n aumenta.
Esses exemplos de código demonstram as diferentes complexidades de tempo e como elas podem afetar o desempenho do algoritmo com base no tamanho dos dados de entrada.
Saudações!
Para saber mais: