8 Complexidade computacional

Neste capítulo, veremos noções básicas de complexidade de algoritmos. Note que não estudaremos formalmente ou profundamente os conceitos. O objetivo é prover intuição sobre os conceitos principais e habilitar o estudante a entender suas implicações na escolha dos algoritmos.

8.1 Importância da análise de complexidade

Ao planejarmos a solução para um problema computacional, teremos que escolher uma entre várias possíveis alternativas. Diversos aspectos podem ser considerados para escolha, como facilidade de implementação, familiaridade, ou conveniência. No entanto, o ponto muito importante a ser considerado é eficiência do algoritmo.

Podemos definir o conceito de eficiência em termos de dois pontos de vista: de tempo e de memória. Dependendo da situação, as diferenças de eficiência podem:

  • Ser irrelevantes, isto é, ambos os algoritmos possuem eficiência similar para entradas de qualquer tamanho; ou
  • Ser relevantes, isto é, apresentam custos significantemente diferentes, isto é, diferença proporcional ao tamanho da entrada.

Muitas vezes, para pequenos problemas, a diferença entre algoritmos torna-se irrelevante. Por isso, o foco deste capítulo é analisar o custo computacional dos algoritmos assintoticamente, ou seja, para entradas muito grandes.

Veremos, na próxima parte do livro, como estes conceitos se aplicam também na escolha das estruturas de dados.

Exercícios:

  1. Escreva um programa que ordene um vetor numérico com tamanho e valores arbitrários. Derive a função de custo de tempo em função do tamanho do vetor de entrada no pior caso. Indique a ordem de complexidade (notação O-grande) de tempo e de espaço do seu algoritmo.
  2. Escreva um algoritmo para encontrar o menor valor num vetor. Qual a ordem de complexidade de tempo no pior caso?
  3. Escreva um algoritmo para verificar se determinado elemento está num vetor.
    1. Qual a ordem de complexidade de tempo no pior caso do seu algoritmo?
    2. Considerando que o vetor está ordenado, escreva um algoritmo que tem ordem de complexidade \(O(\log n)\).
  4. Escreva um algoritmo recursivo para cálculo do máximo divisor comum (Algoritmo de Euclides). Qual a ordem de complexidade de tempo em função das entradas no pior caso? Dica: procure na literatura a prova que utiliza sequência de Fibonacci.
  5. Considerando as funções do tempo de execução abaixo, indique a ordem de complexidade no pior caso para cada uma delas.
    1. \(2 n + 10\)
    2. \(\frac{1}{3} n (n + 2)\)
    3. \(n + \sqrt n\)
    4. \(n + 100 n^{0.1}\)
    5. \(2^n + 3 n + n^{10}\)
    6. \(n^2 + n \log n\)
    7. \(\log_3 n + \log_2 n\)