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

Como calcular a mediana com complexidade linear na média usando partições?

+2 votos
64 visitas
perguntada Jun 22 em Matemática por JoaoMaria (71 pontos)  
republicada Jun 26 por JoaoMaria

O problema de determinar a mediana de um vetor qualquer \( n \) com é descobrir o \( n/2 \)-ésimo menor elemento do vetor, isto é, o elemento da posição \( n/2 \) quando se considera o vetor ordenado. Uma solução fácil é ordenar o vetor.Entretanto, sabe-se que isso consome \( \Omega (n\log n) \)instruções no pior caso.
É possível fazer melhor ? É possível conseguir a complexidade média linear no cálculo da mediana?

Compartilhe

2 Respostas

+2 votos
respondida Jun 23 por JoaoMaria (71 pontos)  
editado Jun 26 por JoaoMaria

Vamos iniciar explicando o que é complexidade média:
A complexidade média de um algoritmo é a média ponderada do desempenho de cada entrada pela probabilidade dela ocorrer.
Considere um algoritmo a; o conjunto de suas entradas com tamanho n, \( D_n\); e prob(d) a probabilidade de ocorrer a entrada d de D
Assim, a complexidade média do algoritmo a é igual a:
\[c_m [a](n):= \sum _{d_\in D_n} (dED_n) [prob(d) *desemp[a](d)] \]

Nosso algoritmo solução tem como base o algoritmo de partição do Quicksort e é baseado no princípio de divisão e conquista.
Logo, Lembremos que:
a partição \(A[i\dots f]\)
dado o vetor \(A[i\dots f]\) de números inteiros,
com \(i>f\) e \(A[i-1] \le A[i\dots f] \le A[f+1]\).
devolve \(d \in [i\dots f]\) e os elementos de \(A\) rearranjados de modo que
\( A[i \dots d-1]\le A[d] \le a[d+a\dots f]\).

se \(d\) dado por Partição é a mediana, então temos a solução. Por outro lado, se \(d\) é maior que a mediana então continuamos em \(A[1\dots d-1]\), senão continuamos pela procura do \(([ n/2 ] -d)\)-ésimo menor elemento de \(A[d+1\dots n]\).

Como pode ser notado no algorimo codificado abaixo, o custo é quadrático no pior caso. Vamos contar o número de comparações feitas com uma entrada de tamanho \(n\) no pior caso. Notemos que o número de comparações é proporcional ao número de instruções básicas que o algoritmo executa.
No pior caso, \(d\) é sempre a primeira posição do vetor \((i)\), de modo que o número de comparações é:
\(T(n) = T(n-1) + (n+1)\), portanto \(T(n)=O(n^2)\)
Esse custo pode ser melhorado se conseguirmos escolher bem um pivô de modo que a partição seja mais equilibrada. De fato se o tamanho do subproblema na recursão for \(< \alpha n\) para alguma constante \(\alpha < 1\), então:
\(T(n) \le T(\alpha n) + (n+1)\), portanto \(T(n)=O(n)\)
De fato, iterando a recorrência \(i\) vezes
\[T(n) \le T(\alpha^i n) + \alpha^{i-1} n +\dots+\alpha n + i\]
\[ \le T(\alpha^i n) + {( 1- \alpha^i) \over (1- \alpha)} n + i\]
e tomando \(i\) da ordem de \(\log_{1/\alpha}n\) temos \(T(n) \leq c( 1 + n +\log_{1/\alpha}n)\), portanto \(T(n) = O(n)\).
Um modo de escolher o pivô que podemos adotar é como a que ´é foi feita no quicksort probabilístico: escolhemos um elemento do vetor aleatoriamente para ser o pivô.

Abaixo apresentamos o algoritmo codificado:

Bibliotecas importadas

import random

Algoritmo Quicksort codificado em Python, que é a base da nossa soução

def quicksort(a):
    if len(a)==1:
        return a
    else:
        p=a[1]
        a_sup=[]
        a_inf=[]
        for i in range(0,len(a)):
            if a[i]<=p:
                a_inf.append(a[i])
            else:
                a_sup.append(a[i])
        if len(a_sup)==0:
            a_sup.append(a[1])
            a_inf.remove(a[1])
        a_inf = quicksort(a_inf)
        a_sup = quicksort(a_sup)
        at=[]
        for i in range(0,len(a_inf)):
            at.append(a_inf[i])
        for i in range(0, len(a_sup)):
            at.append(a_sup[i])
       # print(at)
        return at

Algoritmo mediana codificado em Python que contem a função de seleciona o enesimo termo da lista

def mediana(lista):
    if len(lista) % 2!=0:
        return selecione_enesimo(len(lista)//2, lista)
    else:
        return (selecione_enesimo((len(lista)-1) // 2, lista)+ selecione_enesimo((len(lista)+1) // 2, lista)) / 2
def selecione_enesimo(n, lista):
    pivot = random.choice(lista)

    subListaMenor = [item for item in lista if item < pivot]
    if len(subListaMenor) > n:
        return selecione_enesimo(n, subListaMenor)
    n -= len(subListaMenor)

    repeticaoPivot = lista.count(pivot)
    if repeticaoPivot > n:
        return pivot
    n -= repeticaoPivot

    subListaMaior = [item for item in lista if item > pivot]
    return selecione_enesimo(n, subListaMaior)

Programa principal, que se encarrega de chamar a função mediana. Também neles é chamada a função quicksort que classifica o vetor e depois calcula a mediana sobre o vetor classificado. Isso é feito para confirmarmos o resultado.

if __name__ == '__main__':

    x=[5, 3, 8, 9, 1, 7, 2, 4, 6, 7]

    print(x)
    print(mediana(x))
    z=quicksort(x)
    print(z)
    if len(z)%2==0:
        med=(z[(len(z)-1)//2]+z[len(z)//2])/2
    else:
        med=z[len(z)//2]
    print (med)
comentou Jun 27 por João Gabriel Souza (76 pontos)  
editado Jun 27 por João Gabriel Souza
Muito boa solução: O exercício está bem didático, formatado corretamente e com resolução reproduzível. Interessante a exposição de linearidade da complexidade do algoritmo.

Apenas com intuito de complementar a resposta, segue uma reprodução de um código de Quicksort mais enxuta que a apresentada na pergunta. O código de Quicksort apresentado no exercício acima demonstra resultado correto. O código a seguir serve só de ilustração de uma solução do mesmo tipo mais enxuta.

O código seguirá na resposta abaixo.
comentou Jul 7 por JoaoMaria (71 pontos)  
Obrigado pela avaliação e sugestão.
incorporarei o código.
+1 voto
respondida Jun 27 por João Gabriel Souza (76 pontos)  

Segue o código de Quicksort.

def quicksort(d):
    if len(d) <= 1:
        return d
    pivot = rd.choice(d)
    equal = [y for y in d if y == pivot]
    lesser = [y for y in d if y < pivot]
    greater = [y for y in d if y > pivot]
    return quicksort(lesser) + equal + quicksort(greater)
...