POSCOMP 2019: Questão 25 Resolvida (Análise de Algoritmos)

Questão

Considere a seguinte função em C:

void funcao(int n){
    int i,j;
    for (i=1; i<=n; i++)
        for(j=1; j<log(i); j++)
            printf("%d",i+j)
}

A complexidade dessa função é:

• (A) $\Theta(n)$
• (B) $\Theta(n\log n)$
• (C) $\Theta(\log n)$
• (D) $\Theta(n^2)$
• (E) $\Theta(n^2\log n)$

Resolução

Numa análise preliminar, poderíamos dizer que a complexidade do algoritmo é de $\Theta(n\log n)$, pois o laço for mais externo na variável i é executado $n$ vezes e o laço interno na variável j é executado quase $\log i$ vezes a cada iteração do laço externo, sendo $n$ o valor máximo de i.

De fato, a complexidade do algoritmo é de $\Theta(n\log n)$, porém precisamos elaborar a resposta com um pouco mais de rigor.

Denotaremos a complexidade da função como $T(n)$. O laço duplo aninhado dessa função pode ser representado por um duplo somatório e a função printf("%d",i+j), que tem complexidade constante, pode ser representada por uma constante $c$ ou podemos simplesmente normalizar e assumirmos $c=1$, já que as constantes são absorvidas pela notação assintótica. Em suma:

$$T(n)=\sum_{i=1}^{n}\sum_{j=1}^{\log(i)-1}1$$

O limite superior do somatório interno na variável $j$ é $\log(i)-1$ porque o bloco de código do laço interno só é executado quando $j<\log(i)$ , ou seja, só até $\log(i)-1$. Continuando a resolução de $T(n)$, temos:

$$\begin{align*}T(n)&=\sum_{i=1}^{n}\sum_{j=1}^{\log(i)-1}1\\&=\sum_{i=1}^{n}(\log(i)-1)\\&=(\log(1)+\log(2)+\log(3)\ldots\log(n))-n\\&=\log(1.2.3\ldots n)-n\\&=\log(n!)-n\\\end{align*}$$

Como o termo $-n$ é assintoticamente menor que $\log(n!)$, então $T(n)=\Theta(\log(n!))$. Pela Aproximação de Stirling [1], $\log(n!)\sim n\log n$. Ou seja,

$$T(n)=\Theta(\log(n!))=\Theta(n\log n).$$

Portanto, a alternativa correta é a B.

Mais questões

Se você deseja mais questões resolvidas do POSCOMP 2019, acesse a tag Questões do POSCOMP 2019.

Agora, se você procura questões, gabaritos e caderno de questões de outras edições, então acesse a página POSCOMP.

Resolverei as questões conforme o tempo permitir e de acordo com os meus conhecimentos. Como eu não sei resolver todas as questões, recomendo que você consulte também o gabarito oficial do exame.

Referências

[1] Weisstein, Eric W. Stirling's Approximation. From MathWorld (A Wolfram Web Resource).