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\]
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
ou
. Vamos usar análise de loops para cada caso: divisão por
, aninhamento de loops dependente de condição e multiplicação por
.
Passo 2
Análise de CALC:
- A variável
inicia em e a cada iteração é atualizada para . - O loop continua enquanto
. - O número de iterações
satisfaz
- Cada iteração faz operações de soma e divisão (constantes), então
Passo 3
Análise de
(
):
- O loop externo roda
vezes ( até ). - Se
, em cada iteração interna há um loop de até , ou seja, mais iterações. Total de operações de impressão: . - Se
, em cada uma das iterações externas faz-se apenas uma impressão, total . - Logo, no pior caso (quando
)
e no melhor caso (quando
)
Passo 4
Análise de ALG(
):
- A variável
inicia em e dobra a cada passo ( ) até . - O número de iterações
satisfaz
- Assim
Resposta
CALC:
: pior caso
, melhor caso
ALG:
ALG: