Considere um algoritmo composto por comandos primitivos e dois loops aninhados com contadores independentes. O loop mais externo tem M repetições enquanto que o loop interno tem N repetições. O que podemos afirmar sobre o tempo do algoritmo? Qual seria o seu tempo se os loops fossem invertidos (loop mais interno se tornasse o mais externo e vice-versa)?

Passo 1

O enunciado apresenta um algoritmo formado por comandos primitivos e dois loops aninhados cujos contadores são independentes. O loop externo repete M vezes e, para cada iteração dele, o loop interno repete N vezes. O conteúdo da matéria é análise de complexidade de tempo em algoritmos.

Passo 2

Para estimar o tempo total, note que o corpo do loop interno será executado exatamente uma vez para cada par (i,j) com i\in\{1,\dots,M\} e j\in\{1,\dots,N\}. Se cada execução do corpo custa tempo constante c, então
T(M,N) = \sum_{i=1}^{M}\sum_{j=1}^{N} c = c\,M\,N.
Em notação assintótica isso dá
T(M,N)\in\Theta(MN).

Passo 3

Se invertermos a ordem dos loops — isto é, o loop que antes era interno (com N repetições) passa a ser externo, e vice-versa — a contagem de execuções do corpo continua sendo todos os pares (i,j) com i\in\{1,\dots,M\}, j\in\{1,\dots,N\}. Logo, ainda temos
T(N,M) = c\,N\,M = c\,M\,N \quad\Longrightarrow\quad T(N,M)\in\Theta(MN).

Resposta

O tempo do algoritmo é \Theta(MN) e permanece \Theta(MN) mesmo se os loops forem invertidos.

Exercícios relacionados