Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Quais são formas de resolver o problema de encontrar o máximo de uma sequência usando recursão?

+2 votos
54 visitas
perguntada Mai 6, 2016 em Ciência da Computação por Saulo (426 pontos)  

Resolva o problema de encontrar o máximo de uma sequência usando recursões:
a) Escreva uma recursão usando a estratégia reduza e conquiste.
b) Escreva agora uma recursão baseada em divida e conquiste.
c) Qual complexidade desses algoritmos?

Compartilhe

1 Resposta

+3 votos
respondida Mai 6, 2016 por Saulo (426 pontos)  

Letra (a):

def obter_maximo_a(x, i=0, valor_maximo=0):
    if (i == 0):
        valor_maximo = x[0]
    else:
        if (x[i] > valor_maximo):
            valor_maximo = x[i]

    if (i+1 < len(x)):
        return obter_maximo_a(x, i+1, valor_maximo)
    else:
        return valor_maximo

Letra (b):

def obter_maximo_b(x):
    n = len(x)
    if (n > 1):
        n_middle = int(n/2)
        A = copy.deepcopy(x[0:n_middle])
        B = copy.deepcopy(x[n_middle:n])
        max_A = obter_maximo_b(A)
        max_B = obter_maximo_b(B)
        return merge_maximo(max_A, max_B)
    else:
        return x[0]

def merge_maximo(max_A, max_B):
    if (max_A > max_B):
        return max_A
    else:
        return max_B

Para verificar as soluções:

if __name__ == '__main__':

    N = 10
    x = list( ((N**2)*np.random.rand(N)).astype(int) )
    print x

    print obter_maximo_a(x)

    print obter_maximo_b(x)

Letra (c)

Complexidade do item (a): \( O(n) \)
\( \begin{array}{rcl}
T(n) & = & T(n-1) + O(1) \\
~ & = & T(n-2) + 2O(1) \\
\vdots & ~ & \vdots \\
~ & = & T(n-i) + iO(1) \\
\vdots & ~ & \vdots \\
~ & = & T(n-n) + nO(1)
\end{array}
\)
\( \Rightarrow T(n) \in O(n) \)

Complexidade do item (b): \( \Theta(n) \)
\( T(n) = 2T(n/2) + f(n) \), com \( f(n) \in O(1) \)
Usando Master theorem, como \( f(n)= O(n^{\log_{2}{2}-\varepsilon}) \), com \( \varepsilon=1 \), então \( T(n) \in \Theta(n^{\log_{2}{2}})=\Theta(n) \)

Algum erro? Favor me avisar. Dúvidas e sugestões são sempre bem-vindos!

...