Complexidade de encontrar o maior

O que segue é o meu algoritmo para fazer isso no que acredito ser $O(n)$tempo e minha prova disso. Meu professor discorda que seja executado em$O(n)$ e, em vez disso, pensa que é executado em $\Omega(n^2)$Tempo. Quaisquer comentários sobre a prova em si ou o estilo (ou seja, minhas idéias podem ser claras, mas a apresentação não).

A pergunta original:

Dado $n$ números, encontre o maior $m \leq n$ entre eles a tempo $o(n \log n)$. Você não pode assumir mais nada sobre$m$.

Minha resposta:

1. Classifique o primeiro $m$elementos da matriz. Isso leva$O(1)$ tempo, pois isso depende totalmente da $m$, não $n$.
2. Armazene-os em uma lista vinculada (mantendo a ordem classificada). Isso também leva$O(1)$ pelo mesmo motivo acima.
3. Para todos os outros elementos da matriz, teste se é maior que o menor elemento da lista vinculada. Isso leva$O(n)$ tempo como $n$ comparações devem ser feitas.
4. Se o número for realmente maior, exclua o primeiro elemento da lista vinculada (a mais baixa) e insira o novo número no local que manteria a lista na ordem classificada. Isso leva$O(1)$ tempo porque é limitado por uma constante ($m$) acima, pois a lista não cresce.
5. Portanto, a complexidade total do algoritmo é $O(n)$.

Estou ciente de que o uso de uma árvore vermelho-preta em oposição à lista vinculada é mais eficiente em termos constantes (como o limite superior constante é $O(m\cdot \log_2(m))$ em oposição a $m$ e o problema de manter um ponteiro para o elemento mais baixo da árvore (para facilitar as comparações) é eminentemente possível, simplesmente não me ocorreu na época.

Qual é a minha prova que está faltando? Existe uma maneira mais padrão de apresentá-lo (mesmo que esteja incorreto)?

Aqui está um $O(n)$ algoritmo que resolve o problema.

1. Use o pior caso $O(n)$ algoritmo de seleção para determinar a$n-m+1$estatísticas de terceira ordem. Deixei$k$ seja esse número, que é o menor dos $m$ maiores números que estamos tentando determinar.

2. Agora particione a matriz em torno do pivô $k$usando a partição QuickSort função de . Este passo leva$O(n)$ também.

3. Saída do $m$ números maiores: são dados por $k$ e todos os números na sub-matriz superior gerados pela partição na etapa 2.

Seu algoritmo leva $\Theta(n + mn)$Tempo. Eu suspeito que seu professor está procurando algo que leva$O(n+ n\log m)$ tempo, o que deve ser possível, talvez usando uma pilha ...

A fonte de sua discordância com o professor é que ele ou ela não parece pensar $m$é uma constante, apesar de como a pergunta está formulada. Se não for, então$\Theta(m)$ é muito pior que $\Theta(\log m)$.

Correção
Falta na sua apresentação é o loop invariável para estabelecer a correção: você mantém a maior$m$elementos encontrados até o momento em uma lista vinculada. Assim, no final do seu algoritmo, você testou todos os elementos e, portanto, possui o maior$m$elementos na matriz. Seu algoritmo ainda está correto, mas declarar o objetivo da lista vinculada no início da descrição torna sua correção mais explícita.

Tempo de execução
$log_{10}( 10 \mbox{ billion}) = 10$, (na base 2, é aproximadamente ~ 33), o que é muito menor que 10 milhões. No exemplo dado,$m$ é muitas vezes maior que $\log n$e, portanto, não acho que você possa assumir com segurança que $m$ é constante.

Você deve fornecer um algoritmo que seja $o(n \log n)$ enquanto $m = o(n)$. Substituir sua lista vinculada e pesquisa linear por uma árvore de pesquisa binária equilibrada ou um min-heap alcançará este tempo de execução:$O(m \log m + n \log m) = O(n \log m) = o(n \log n)$. (assumindo$m = o(n)$, caso contrário, seu tempo de execução é $\Theta(n \log n)$)

Caso você não esteja familiarizado com a notação, a intuição por trás $o(n \log n)$ é $< O(n \log n)$, mas consulte a pergunta correspondente em cs.SE para obter detalhes da notação.