Encontrar o mais alto 2 ciência da computação numbers-

Question

Eu estou tentando descobrir um algoritmo para encontrar os mais altos 2 números em uma lista de números.

O número mais alto pode ser encontrado em n-1 etapas, talvez fazendo o primeiro passo de uma espécie de bolha ou algo nesse sentido. Para mim, parece que encontrar o número mais elevado seguinte, bem poderia ser encontrado em um total de 1,5 N comparações em média.

Meu professor definir-nos a lição de casa para escrever um alogrithm que encontra os mais altos 2 números em n + log (n) comparações. Isto é mesmo possível? Todas as ideias, sugestões?

Editar: Quando eu digo n + log (n) eu não estou me referindo a O (n + log n), mas sim exatamente n + log n

Answer 1

Sim, é possível fazê-lo em não mais do que (n + log n). Eu realmente não posso dizer-lhe como sem dar a resposta, mas deixe-me tentar. :-)

Leve os números n, compará-los em pares de cada vez. Leve o ceil (n / 2) "vencedores", e repita, "como uma árvore binária". Perguntas: quantas comparações que é preciso para encontrar o maior? Quantas pessoas é que esta "vencedor" vencer? A quem pode o segundo maior perderam? Então, quantas comparações ele agora tomar para encontrar o segundo maior número?

A resposta acaba por ser um total de n-1 + teto (log n) - 1 comparações, onde o log é a base 2. Você também pode provar usando um argumento contraditório que não é possível fazer melhor do que isso, no pior caso.

Answer 2

Editar: Opa, perdeu uma coisa simples, devido à estupidez. Esta solução não é correto, embora eu estou mantendo-lo aqui como ainda é avg (n + log (n)). Graças à ShreevatsaR para apontar minha estupidez. Eu fiz considerar a busca árvore, mas completamente perdido a idéia de retrocesso para encontrar o segundo número mais alto no log (n).

De qualquer forma, aqui segue a minha prova de por que o algoritmo inferior não mais do que avg (n + log (n)) é. Na vida real, ele ainda deve executar muito bem, pelo menos.

• Primeiro comparar com o segundo número mais alto registrado.
• Somente se que a comparação for bem sucedida, comparar com o número mais alto registrado.

Para provar que é, em média, n + log N, nós simplesmente temos que provar que a primeira comparação só consegue log vezes (n), em média. E isso é bastante simples de ver ou demonstrar.

1. Suponha P como a posição real da corrente segundo maior número em uma versão ordenada da lista, e executar o algoritmo
2. Se P> 2, em seguida, quando um número maior for encontrado, o novo testamento P, em média, ser superior a P / 2.
3. Se P = 2, então a primeira comparação pode não ter sucesso, porque não há nenhum número que é maior do que a segunda corrente maior número.
4. P pode, no máximo, igual N
5. A partir de 2, 3 e 4 deve ser trivial para ver que a primeira comparação não pode ter sucesso mais de log vezes (N), em média.

Answer 3

Como sobre isto:

for each listOfNumbers as number
    if number > secondHighest
        if number > highest
            secondHighest = highest
            highest = number
        else
            secondHighest = number

Answer 4

A resposta postado por ShreevatsaR parece ser O (n log n).

A primeira passagem (n operações) produz n / 2 respostas. Repetindo, eu acho que você quer dizer que você vai fazer n / 2 operações para produzir n / 4 respostas. Você vai passar por log do loop n vezes. Isto é muito parecido com um merge sort, exceto que merge sort sempre processa n nós cada vez completamente. Também é executado o log do ciclo n vezes. E eu não vejo como esse algoritmo irá acompanhar o segundo número higest.

nickf tem a resposta certa. pior caso é quando a lista é ordenada, ele vai fazer comparações 2n -. que é O (n)

aliás, S (N + log n) é O (n) a notação pedido refere-se a pior caso crescimento assintótica.

Answer 5

Você pode usar contando tipo, radix sort, balde algoritmo de tempo linear tipo ou outro de primeiro ordenar a lista em ordem decrescente. Então é só pegar os 2 primeiros elementos da lista ordenada. Então, isso vai levar (n) + 2 = (n)

Note que este algoritmo pode classificar em tempo linear porque cada um tem suas próprias premissas.

Answer 6

Pseudocódigo (não é esse essencialmente n?)

int highestNum = 0
int secondHighest = highestNum

for(i = 0; i < list.length; i++)
{
if(list[i] >= highestNum)
{
secondHighest = highestNum
highestNum = list[i]
}
}