Calcule a complexidade, no pior caso, do fragmento de código abaixo:
int i,j,k,s;
for(i=0; i < N-1; i ++)
for(j=i +1; j < N; j++)
for(k=1; k < j; k++)
s = 1;
int i,j,k,s;
for(i=0; i < N-1; i ++)
for(j=i +1; j < N; j++)
for(k=1; k < j; k++)
s = 1;
Passo 1
O enunciado pede pra calcular, no pior caso, a complexidade de tempo de um trecho em C que tem três loops aninhados. O conteúdo da matéria é análise de algoritmos, em particular conversão de loops em somatórios e uso de fórmulas de séries aritméticas para encontrar a ordem de crescimento.
Passo 2
Pra contar quantas vezes o corpo (a atribuição de s) é executado, a gente escreve um somatório triplo que reflete cada loop em i, j e k. Assim temos:
Passo 3
O próximo passo é simplificar o somatório sobre k, pois para cada par (i,j) o loop em k faz exatamente j−1 iterações. Logo:
E portanto
Passo 4
Agora a gente calcula o somatório interno em j usando soma de termos de progressão aritmética. Primeiro separamos:
Pelo fórmula da soma de 1 até M temos
. Aplicando de j=
até
e simplificando, obtém-se uma expressão polinomial em N e i de grau 2.
Passo 5
Finalmente, ao somar essa expressão sobre i de 0 até N−2, a gente gera um polinômio de grau 3 em N. O termo de maior ordem vem de integrar
sobre i e j, resultando em uma constante vezes
. Logo a complexidade, no seu termo dominante, cresce como
.