Idéa indutiva:
- Caso base: Se o valor que será convertido for igual a 0 ou 1, então o problema está automaticamente resolvido.
- Hipótese de indução: Nós podemos assumir que já temos os n - 1 bits que compõem a representação binária. Pode até parecer uma suposição absurda, mas é dessa forma que a indução trabalha =D.
- Caso geral: Agora basta estender a solução adicionando o último bit ao final da resposta que a hipótese de indução nos deu. E assim como acontece na prova de um teorema, a utilização da hipótese de indução no passo indutivo é obrigatória.
- Implementação em Haskell
dec2bin :: Int -> String dec2bin 0 = "0" dec2bin 1 = "1" dec2bin n = dec2bin(n `div` 2) ++ show(n `mod` 2)
- Implementação em Python
def dec2bin(n): if n < 2: print (n), else: dec2bin(n / 2) print (n % 2),
- Implementação em Java
public static void dec2bin(int n) { if (n < 2) { System.out.println(n); } else { dec2bin(n / 2); System.out.println(n % 2); } }
- Implementação em JavaScript
function dec2bin(a) { if(a < 2) return a; else return dec2bin(Math.floor(a / 2)) + “” + (a % 2); }
- Implementação em C++
void dec2bin(int n){ if(n < 2) cout << n; else { dec2bin(n / 2); cout << (n % 2); } }O tempo de execução do algoritmo apresentado aqui é expresso pela relação de recorrência T(n) = T(n/2) + 1.
Fazendo n = $2^k$, temos
$T(n) = T(2^{k-1}) + 1$
$T(n) = T(2^{k-2}) + 1 + 1$
$T(n) = T(2^{k-3}) + 1 + 1 + 1$
$T(n) = T(2^{k-4}) + 1 + 1 + 1 + 1$
....
$T(n) = T(2^0) + 1 + 1 + 1 + 1 + 1 + 1 + ... + 1 + 1$
$T(n) = k$
Como $n = 2^k$, temos que $log n = log 2^k$ e $log n = k$, então a complexidade do método é limitada assintoticamente pela função logarítmica. Ou seja, $T(n) = O(log n)$.
Nenhum comentário:
Postar um comentário