Para o cálculo da complexidade de algoritmos não recursivos, existe um conjunto de regras bastante simples de serem seguidas. Cite e descreva estas regras.

Passo 1

O enunciado pede para listar e descrever as regras usadas na análise de complexidade de algoritmos não recursivos (conteúdo: análise assintótica e notação O-grande).
Antes de citar as regras, é bom lembrar que usamos a notação O-grande para expressar o crescimento de funções de custo quando o parâmetro de entrada tende ao infinito, desprezando detalhes de implementação e focando na ordem de grandeza.

Passo 2

Regra 1 (Operação Elementar): toda instrução básica (atribuição, soma, comparação, etc.) é considerada de custo constante, ou seja, O(1).

Passo 3

Regra 2 (Composição Sequencial – Soma): para trechos executados em sequência, a complexidade total é dada pela soma das complexidades de cada trecho. Como O(f(n)) + O(g(n)) = O(f(n) + g(n)), o termo dominante prevalece.

Passo 4

Regra 3 (Estrutura Condicional – Máximo): para um if/else, a complexidade do bloco é o máximo entre as complexidades dos dois ramos, pois não sabemos qual executará. Assim, O(if) = O(max(f(n), g(n))).

Passo 5

Regra 4 (Laço Simples – Produto): num loop que repete k vezes um corpo de complexidade O(f(n)), a complexidade total é O(k·f(n)). Se k depende de n (por exemplo, k=n), temos O(n·f(n)).

Passo 6

Regra 5 (Laços Aninhados – Produto de Ordens): quando há loops aninhados, a complexidade é o produto das complexidades de cada nível. Por exemplo, dois loops de 1 a n aninhados dão O(n)·O(n)=O(n²).

Passo 7

Regra 6 (Simplificação Assintótica): depois de combinar soma e produto, simplificamos a expressão final descartando constantes multiplicativas e termos de ordem inferior, ficando apenas com o termo de maior crescimento.

Resposta

As principais regras para calcular a complexidade de algoritmos não recursivos são:
  1. Operações Elementares: O(1)
  2. Composição Sequencial (Soma): O(f(n)+g(n)) = O(termo dominante)
  3. Estruturas Condicionais (Máximo): O(max(f(n),g(n)))
  4. Laços Simples (Produto): O(k·f(n)), onde k é número de iterações
  5. Laços Aninhados (Produto de Ordens): produto das ordens de cada loop (ex.: O(n)·O(n)=O(n²))
  6. Simplificação Assintótica: descartar constantes e termos de ordem inferior, mantendo o termo de maior crescimento.

Exercícios relacionados