Calcula a complexidade exata das seguintes funções abaixo
function CALC()
\[a=0\]

\[i=N\]
    while \(i>0\) do
\[a=a+i\]

\[i=i / 2\]
function CRAZY_FUNC( \(\mathrm{n}, \mathrm{x}, \mathrm{y}\) )
    for \(i=0, i<n,++i\) do
        if \(x<y\) then
            for \(k=0, k<n,++k\) do
                \(\operatorname{print}(k)\)
        else
            print \((i)\)
function \(\operatorname{ALG}(\mathrm{n})\)
\[j=1\]
    while \(j<n\) do
\[j=j * 2\]

Passo 1

O enunciado pede para determinar a complexidade de tempo exata de três funções em termos de n ou N. Vamos usar análise de loops para cada caso: divisão por 2, aninhamento de loops dependente de condição e multiplicação por 2.

Passo 2

Análise de CALC:
  • A variável i inicia em N e a cada iteração é atualizada para i/2.
  • O loop continua enquanto i>0.
  • O número de iterações k satisfaz
\frac{N}{2^k}\le1 \quad\Longrightarrow\quad 2^k\ge N \quad\Longrightarrow\quad k=\bigl\lceil\log_2 N\bigr\rceil.
  • Cada iteração faz operações de soma e divisão (constantes), então
T(N)=\Theta\bigl(\log N\bigr).

Passo 3

Análise de CRAZY_FUNC( n,x,y):
  • O loop externo roda n vezes ( i=0 até i=n-1).
  • Se \;x<y, em cada iteração interna há um loop de k=0 até k=n-1, ou seja, mais n iterações. Total de operações de impressão: n\times n=n^2.
  • Se \;x\ge y, em cada uma das n iterações externas faz-se apenas uma impressão, total n.
  • Logo, no pior caso (quando x<y)
T(n)=\Theta\bigl(n^2\bigr),
e no melhor caso (quando x\ge y)
T(n)=\Theta(n).

Passo 4

Análise de ALG( n):
  • A variável j inicia em 1 e dobra a cada passo ( j\gets j\cdot2) até j\ge n.
  • O número de iterações k satisfaz
2^k\ge n \quad\Longrightarrow\quad k=\bigl\lceil\log_2 n\bigr\rceil.
  • Assim
T(n)=\Theta\bigl(\log n\bigr).

Resposta

CALC: \Theta(\log N) CRAZY_FUNC: pior caso \Theta(n^2), melhor caso \Theta(n)
ALG: \Theta(\log n)

Exercícios relacionados