0

Alguém poderia me explicar como se calcula o T(n) desse algoritmo sendo n >= 0? Já vi vídeos e aulas e não estou conseguindo entender como funciona esse cálculo.

T(n) de um algoritmo é o quanto de operações primitivas ele precisa fazer para uma entrada de tamanho n.

int fib(int n){
    int ant, preant, atual, i;
    if(n>=2){
        ant = 1;
        preant = 1;
        for(i=n; i >=3; i--){
            atual = ant + preant;
            preant = ant;
            ant = atual;
        }
        return atual;
    } else {
        return n;
    }
}
2
  • O que é o T(n)? Commented 26/11/2018 às 19:52
  • T(n) é o cálculo do algoritmo considerando as operações primitivas Commented 26/11/2018 às 20:19

2 Respostas 2

4

Você pode pensar de maneira indutiva seguindo os passos do seu algoritmo. Para tornar a explicação mais simples vou desconsiderar o saldo como uma instrução primitiva, apenas levarei com consideração a comparação, adição, subtração e retorno, entretanto a lógica segue a mesma quaisquer operações que decidir considerar (ou desconsiderar).

Vamos começar com casos em que n < 2, no caso T(0) e T(1):

Temos então uma comparação de n >= 2: consideraremos 1 custo. A instrução é falsa então salta para return n também daremos custo 1. Assim segue que T(n < 2) = 2, para esses casos executa apenas duas instruções.

Agora estamos interessados quanto temos uma entrada n muito grande, pois quanto maior o n mais vezes o laço será executado e portanto mais instruções.

Primeiro vamos considerar os custos constantes para uma entrada n muito grande:

  1. comparação n >= 2

  2. ant = 1

  3. preant = 1

  4. i = n é executado uma vez para entrar no laço

  5. comparação i >= 3 será feita ao menos uma vez para determinar se entrará no laço

  6. return atual sempre será executado uma vez

Assim temos 6 instruções que sempre serão executadas para um n muito grande. Agora vamos para as instruções do laço que serão executadas conforme o valor de n:

  1. ant + preant (considerando a soma)

  2. atual = ant + preant (estamos considerando apenas a atribuição a soma já foi considerada)

  3. preant = ant

  4. ant = atual

  5. i--

  6. i >= 3 a comparação será executada toda vez que retornar ao topo do laço

Sendo assim temos 6 instruções que serão executadas conforme o tamanho do n. Agora devemos nos atendar as instruções i = n e i >= 3 (parada), sendo assim o laço n-2 vezes. Portanto a recorrência do algoritmo é:

T(n) = 6 + 6(n - 2) 
T(n) = 6 + 6n - 12
T(n) = 6n - 6

Você pode fazer alguns casos testes com entras pequenas para acompanhar esse método, também pode escolher considerar as instruções de salto ou desconsiderar as instruções de retorno por exemplo, em todo caso o método permanece o mesmo.

1
  • Você me fez ver um erro na minha resposta =) Commented 28/11/2018 às 0:56
4

Esse algoritmo apresentado é muito semelhanteleia observação no final da resposta a uma implementação do algoritmo para calcular o número n da sequência de Fibonacci, que por sua vez tem complexidade temporal linear (o(n)). Então, dá pra dizer que o comportamento esperado de T(n) seja uma função linear, no formato T(n) = a*n + b, para casos gerais. Porém, existem casos especiais: qualquer número com n <= 1 tem T(n) = 2. Como sei disso? Fazendo o teste de mesa. Veja como foi para n = 1:

  1. verifica valor da posição -1 >= 2 (n >= 2)
  2. retorne valor da posição -1 (return n)

Estou considerando que o goto seja parte da operação primitiva de comparação, algo como jumpelse n >= 2, LABEL_ELSE

Agora, como seria para um outro caso? Para um caso genérico de n? Testemos com n = 4:

  1. verifica valor da posição -1 >= 2 (n >= 2)
  2. atribui 1 à posição 0 (ant = 1)
  3. atribui 1 à posição 1 (preant = 1)
  4. atribui valor da posição -1 à posição 3 (i = n)
  5. verifica se valor da posição 3 >= 3 (i >= 3)
  6. soma valor da posição 0 e valor da posição 1 (ant + preant)
  7. atribui resultado à posição 2 (atual = ant + preant, sendo que a soma foi considerada acima)
  8. atribui valor da posição 1 à posição 0 (preant = ant)
  9. atribui valor da posição 2 à posição 1 (ant = preant)
  10. decrementa a posição 3 (i--)
  11. verifica valor da posição 3 >= 3 (i >= 3)
  12. soma valor da posição 0 e valor da posição 1 (ant + preant)
  13. atribui resultado à posição 2 (atual = ant + preant, sendo que a soma foi considerada acima)
  14. atribui valor da posição 1 à posição 0 (preant = ant)
  15. atribui valor da posição 2 à posição 1 (ant = preant)
  16. decrementa a posição 3 (i--)
  17. verifica valor da posição 3 >= 3 (i >= 3)
  18. retorna valor da posição 2 (return atual)

Então, deram 18 operações para n = 4. E para n = 5?

  1. verifica valor da posição -1 >= 2 (n >= 2)
  2. atribui 1 à posição 0 (ant = 1)
  3. atribui 1 à posição 1 (preant = 1)
  4. atribui valor da posição -1 à posição 3 (i = n)
  5. verifica se valor da posição 3 >= 0 (i >= 0)
  6. soma valor da posição 0 e valor da posição 1 (ant + preant)
  7. atribui resultado à posição 2 (atual = ant + preant, sendo que a soma foi considerada acima)
  8. atribui valor da posição 1 à posição 0 (preant = ant)
  9. atribui valor da posição 2 à posição 1 (ant = preant)
  10. decrementa a posição 3 (i--)
  11. verifica valor da posição 3 >= 0 (i >= 0)
  12. soma valor da posição 0 e valor da posição 1 (ant + preant)
  13. atribui resultado à posição 2 (atual = ant + preant, sendo que a soma foi considerada acima)
  14. atribui valor da posição 1 à posição 0 (preant = ant)
  15. atribui valor da posição 2 à posição 1 (ant = preant)
  16. decrementa a posição 3 (i--)
  17. verifica valor da posição 3 >= 0 (i >= 0)
  18. soma valor da posição 0 e valor da posição 1 (ant + preant)
  19. atribui resultado à posição 2 (atual = ant + preant, sendo que a soma foi considerada acima)
  20. atribui valor da posição 1 à posição 0 (preant = ant)
  21. atribui valor da posição 2 à posição 1 (ant = preant)
  22. decrementa a posição 3 (i--)
  23. verifica valor da posição 3 >= 0 (i >= 0)
  24. retorna valor da posição 2 (return atual)

Deu 24 operações. Daqui, conseguimos tirar o valor de a em T(n) = a*n + b e, então, descobriremos b:

T(5) = a*5 + b
T(4) = a*4 + b
T(5) = 24
T(4) = 18
T(5) - T(4) = a*5 + b - (a*4 + b) = a 
T(5) - T(4) = 24 - 18 = 6
a = 6
18 = a*4 + b = 6*4 + b = 24 + b
b = -6

Portanto, temos que, para n >= 2, T(n) = 6*n - 6. Portanto:

T(n) = 2 (se n <= 1), 6*n - 6 (se n >= 2)


Esse algoritmo, apesar de ser muito semelhante a uma implementação clássica ao algoritmo que calcula os números da sequência de Fibonacci, contém um erro que o desqualifica como tal. Veja, por exemplo, o comoportamento para n = 2:

  1. verifica valor da posição -1 >= 2 (n >= 2)
  2. atribui 1 à posição 0 (ant = 1)
  3. atribui 1 à posição 1 (preant = 1)
  4. atribui valor da posição -1 à posição 3 (i = n)
  5. verifica se valor da posição 3 >= 3 (i >= 3)
  6. retorna valor da posição 2 (return atual)

Em nenhum momento a posição 2 (que representa a variável atual) foi preenchida. Isso indica que, nesse momento, o retorno da função é indefinido. Isso é proibido em algumas linguagens de programação, mas os compiladores de C que conheço permitem isso. Em muitos casos, o retorno será um lixo de memória, um valor qualquer, que as vezes pode até coincidir com o valor adequado. Em outras vezes, alguns interpretadores que vi por aí inicializam variáveis com 0. Ademais, veja o resultado da saída para alguns números:

fib(0) => 0
fib(1) => 1
fib(2) => undefined
fib(3) => 2
fib(4) => 3
fib(5) => 5

Existem algumas soluções para corrigir o algoritmo:

  • tornar 2 um caso especial e forçar retornar 1
  • fazer preant = 0, ant = 1 e o laço até i >= 2

A primeira solução adicionaria 1 passo a mais nos casos especiais (e nenhum no caso geral, se bem escrito o algoritmo); também alteraria a composição da função, sendo constante no intervalo (-infty, 2] e linear em [3, +infty) (a original é constante no intervalo (-infty, 1] e linear em [2, +infty)).

A segunda solução não altera o número de passos nos casos especiais, nem tampouco os intervalos que definem o comportamento da função, mas alteraria a parte linear; sairia de 6*n - 6 para 6*n, já que pelo menos um laço (que por sua vez tem 6 operações) será sempre executado.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .