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.
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:
- Operações Elementares: O(1)
- Composição Sequencial (Soma): O(f(n)+g(n)) = O(termo dominante)
- Estruturas Condicionais (Máximo): O(max(f(n),g(n)))
- Laços Simples (Produto): O(k·f(n)), onde k é número de iterações
- Laços Aninhados (Produto de Ordens): produto das ordens de cada loop (ex.: O(n)·O(n)=O(n²))
- Simplificação Assintótica: descartar constantes e termos de ordem inferior, mantendo o termo de maior crescimento.