Apresente os algoritmos recursivos de busca linear e busca binária. Faça uma análise da
complexidade desses algoritmos, definindo a equação de recorrência e aplicando o método
iterativo (árvore de recursão) e o método mestre (se possível).
Envie sua primeira dúvida gratuitamente aqui no Tira-dúvidas Profes. Nossos professores particulares estão aqui para te ajudar.
Busca Linear Recursiva:
função buscaLinearRecursiva(vetor, inicio, fim, chave) retorna inteiro
se inicio > fim então
retorne -1 // a chave não foi encontrada
senão se vetor[inicio] == chave então
retorne inicio // a chave foi encontrada no início do vetor
senão
retorne buscaLinearRecursiva(vetor, inicio + 1, fim, chave) // busca recursivamente no restante do vetor
A complexidade desse algoritmo é O(n), onde n é o tamanho do vetor. A equação de recorrência para o caso médio é T(n) = T(n-1) + 1, e para o pior caso é T(n) = T(n-1) + 2, já que em cada chamada recursiva, a função faz uma comparação e uma adição ou subtração. Aplicando o método iterativo (árvore de recursão), temos:
T(n) = T(n-1) + 1
= T(n-2) + 2
= T(n-3) + 3
...
= T(0) + n
T(n) = n + 1
Assim, a complexidade de busca linear recursiva é O(n).
Busca Binária Recursiva:
função buscaBinariaRecursiva(vetor, inicio, fim, chave) retorna inteiro
se fim < inicio então
retorne -1 // a chave não foi encontrada
senão
meio = (inicio + fim) / 2 // encontra o meio do vetor
se vetor[meio] == chave então
retorne meio // a chave foi encontrada no meio do vetor
senão se vetor[meio] > chave então
retorne buscaBinariaRecursiva(vetor, inicio, meio - 1, chave) // busca recursivamente na metade esquerda do vetor
senão
retorne buscaBinariaRecursiva(vetor, meio + 1, fim, chave) // busca recursivamente na metade direita do vetor
A complexidade desse algoritmo é O(log n), onde n é o tamanho do vetor. A equação de recorrência é T(n) = T(n/2) + 1, já que em cada chamada recursiva, o tamanho do vetor é dividido pela metade e é feita uma única comparação. Aplicando o método mestre, temos a = 1, b = 2 e d = 0, logo log a na base b é igual a d, e a complexidade é O(n^d log n) = O(log n).
Em resumo, a busca linear recursiva é menos eficiente do que a busca binária recursiva em grandes conjuntos de dados, já que a complexidade da busca linear é linear em relação ao tamanho do vetor, enquanto a complexidade da busca binária é logarítmica.
Envie sua primeira dúvida gratuitamente aqui no Tira-dúvidas Profes. Nossos professores particulares estão aqui para te ajudar.
função busca_linear_recursiva(lista, valor, índice):
se índice for igual ao comprimento da lista:
retorne -1 // valor não encontrado
se lista[índice] for igual a valor:
retorne índice // valor encontrado
senão:
retorne busca_linear_recursiva(lista, valor, índice + 1)
--------------------------------------- equacao ----------------------------------
T(n) = T(n-1) + c
------------------------------------------ java -------------------------------------
função buscaBinariaRecursiva(arr, inicio, fim, x)
se fim >= inicio então
meio = inicio + (fim - inicio) / 2
se arr[meio] = x então
retorne meio
se arr[meio] > x então
retorne buscaBinariaRecursiva(arr, inicio, meio-1, x)
retorne buscaBinariaRecursiva(arr, meio+1, fim, x)
retorne -1
87
horas
de aula
995
tarefas
resolvidas
19
horas
de aula
11
tarefas
resolvidas
Envie sua primeira dúvida gratuitamente aqui no Tira-dúvidas Profes. Nossos professores particulares estão aqui para te ajudar.
Aulas
Buscar
Tarefas
Pedir
Turmas
Procurar
Profes Já
Pedir
Cursos
Encontrar
Tira-dúvidas
Enviar dúvida
