3

Preciso analisar o consumo de tempo do meu algoritmo, para um vetor de tamanho n = f - i + 1, através de uma recursão, para então definir uma formula fechada.

public class ehpalindromo {
    public static boolean ehPalindromo(String palavra, int i, int f) {
        //verificar se palavra vazia é vetor unitário com espaço ou vetor vazio(enter)
            boolean iguais = palavra.charAt(i) == palavra.charAt(f); //t1 + t2
            return iguais && (f - i <= 2 ? true : ehPalindromo(palavra, i + 1, f - 1)); //t3 + t4 + t5 + (t6) 
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Digite uma palavra para verificarmos se eh um palindromo ou nao: ");
        String palavra = sc.nextLine();
        System.out.println("Digite o início e o fim da sequência a ser analisada: ");
        int i = sc.nextInt();
        int f = sc.nextInt();
        if(ehPalindromo(palavra, i, f)){
            System.out.println(palavra + " eh palindromo");
        }else {
            System.out.println(palavra + " nao eh palindromo");
        }
    }
}

Primeiro, contei as instruções do algoritmo. Assim, cheguei à seguinte recursão:

F(n) = { a, se n =< 1; a + F(n-2), se n > 1

Base: a, se n =< 1 || Passo: a + F(n-2), se n > 1

Em que "a" corresponde ao somatório das instruções constantes.

Segundo, expandi a recorrência:

F(0) = a;
F(1) = a;
F(2) = a + F(0) = a + a = 2a;
F(3) = a + F(1) = a + a = 2a;
F(4) = a + F(2) = a + 2a = 3a;
F(5) = a + F(3) = a + 2a = 3a;
F(6) = a + F(4) = a + 3a = 4a;

Dessa forma, cheguei, empiricamente, à formula fechada:

F(n) = a + (n/2)a; porém, esta só funciona quando n é par, pois para n impar, ela seria F(n) = a + ((n-1)/2)a.

Gostaria de saber se contei as instruções de forma correta e como proceder para chegar à formula fechada.

8
  • Essa contagem empírica é não confiável. Você deveria usar a prova da indução matemática nesse caso, faltou só o passo indutivo. E você poderia simplificar o resultado de F(n) com a função floor, o arrendondamento para baixo. F(n) = a*(1 + floor(n/2)). Também creio que, dado o curto circuito, a definição da sua F(n) apresente um valor distinto de a na base da recursão 25/09/2017 às 21:30
  • Sem falar que esse é o maior tempo de execução, não palíndromos executam mais rapidamente 25/09/2017 às 21:36
  • Mas já não foram postos o passo indutivo e a base? Como considerar o melhor caso? Sim, preciso usar indução para provar a formula fechada 25/09/2017 às 22:01
  • Se bem que não se usa indução para encontrar a formula fechada, certo? Mas somente para prová-la 25/09/2017 às 22:04
  • 1
    Partindo de F(n) como verdadeiro provo então que F(n+2) também é verdade? Com isso cheguei a F(n+2) = 2a + F(n-2). Estou preso nesse ponto. Faz algum sentido? Como proceder? 25/09/2017 às 22:14

1 Resposta 1

3

Para demonstrar uma fórmula derivada da recorrência, você precisa da conjectura (a fórmula derivada definida acima, que queremos provar) e de 3 outras características:

  1. Fórmula recorrente;
  2. Base da recursão;
  3. Passo indutivo.

Como o AP já demonstrou conhecimento nós dois primeiros pontos, não entrarei em detalhes agora.

Passo indutivo

Suponha que a conjectura funcione para f(x); usando a recursão, provamos que ela também funciona para f(x + 1).

No caso, a conjectura é, para este caso:

F(x) = a*(1 + floor(x/2))

Supondo que seja verdade para F(x). Para avaliar um palíndromo de tamanho x+2, será necessário fazer a passos a mais (dado pela fórmula recorrente). Portanto:

F(x+2) = a + F(x) = a + a*(1 + floor(x/2)) = a*(1+1+floor(x/2)) = a*(1+floor( (x+2)/2 ))

CQD.

O passo indutivo funciona para F(0) e F(1), portanto a conjectura se demonstra correta.

Demonstrar o passo indutivo válido para F(0) e F(1) fica como dever de casa para o leitor ;-)

6
  • Jefferson, o problema está no fato de que não posso utilizar a função floor, pois nossa prova não será programada. Como posso substituí-la? 25/09/2017 às 22:42
  • Usando a notação matemática que parece um colchete sem a parte de cima; en.wikipedia.org/wiki/Floor_and_ceiling_functions?wprov=sfti1; essa é uma função matemática não continua devidamente descrita para os reais e racionais. O Math.floor advém da descrição matemática direta, não é algo inventado apenas no âmbito das linguagens de programação 25/09/2017 às 22:45
  • Então, F(n) = a + F(n-2) também faz parte da base? E não somente F(0) e F(1)? Com isso a recursão seria F(n) = ((n/2)+1)a ? Pode marcar na sua resposta cada uma dessas partes, por gentileza? 25/09/2017 às 22:52
  • Base são só F(0) e F(1), pensei que você já tivesse entendido esse conceito, mas me enganei. F(n) = F(n-2) + a é uma consequência da fórmula recursiva, mas ela só se aplica a n>=2. Para que a fórmula recursiva/recorrência aborde todo o domínio dos naturais, normalmente se escreve F(n+2) = F(n) + a. Com exceção das definições descriminadas acima, todo o resto está na resposta devidamente destacado. Sair de F(0) e F(1) com o passo indutivo foi suprimido da minha resposta por: (a) trivialidade, muito simples fazer; (b) prestar uma ajuda rápida. 25/09/2017 às 23:03
  • 1
    @CaioIgnm , com fórmulas LaTeX deixando tudo mais bonito 28/09/2017 às 2:17

Você deve fazer log-in para responder a esta pergunta.

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