Blz, pessoal, eu tenho que fazer um algoritmo para o problema da mediana. O problema consiste em descobrir, dada uma lista de n números, qual número contém n-1/2 elementos menores e n+1 / 2 maiores na lista. Exemplo, se lsita = (2, 4, 4, 5, 7), mediana é 4. Porém, eu tenho que fazer um algoritmo com complexidade temporal ótima, porém eu não sei qual é, eu acho que é theta(nlogn). Alguém sabe qual é menor complexidade desse problema?
Se a lista estiver ordenada fica fácil encontrar…
Se o número de elementos na lista ordenada for ímpar, a mediana é justamente o valor de n/2.
Se o número de elementos for par, então vc precisa pegar n/2 e n/2+1, somar e dividir por 2.
Me corrija se estiver errado na definição de mediana…hehe
Estando a lista ordenada, a complexidade do algoritmo é constante, representada por theta(1).
Se a lista não estiver ordenada, o tempo ótimo q vc gastará para ordená-la utilizando comparações entre os elementos é theta(nlogn).
Depois de ordenada, o tempo para achar a mediana é constante, então a complexidade final fica sendo o nlogn mesmo.
opa, cara, vlw, to meio fraquin em anaálise de algoritmos e não queria perder tempo fazendo um algoritmo que não fosse de solução ótima, vlw mesmo
A menos que haja um jeito melhor de encontrar a mediana de n elementos sem ter que ordenar a lista, nlogn fica sendo o tempo ótimo. :lol:
não deve haver, meu professor colocou como sugestão, na questão que pede um algoritmo ótimo, ordenar a lista, é isso mesmo, só me faltava confiança 
um ano depois voltando pra dizer q eu estava errado. o algoritmo ótimo é O(n), mas ainda não sei fazer.