A classificação inteira é possível em O (n) no modelo transdicotômico?

Que eu saiba, não existe um algoritmo de pior caso que resolva o seguinte problema: $O(n)$

Dada uma sequência de comprimento consiste em números inteiros finitos, encontre a permutação em que cada elemento é menor ou igual ao seu sucessor. $n$

Mas existe uma prova de que não existe, no modelo transdicotômico de computação ?

Observe que não estou limitando o intervalo dos números inteiros. Também não estou limitando soluções a tipos de comparação.

complexity-theory sorting computation-models lower-bounds orlp
fonte

Tanto quanto eu sei, pode haver um algoritmo de tempo para SAT! Então a resposta é não.

O (n)

$O(n)$

precisa saber é o seguinte

AFAIK, este ainda é um problema em aberto.

21415 Juho

Não sei se pode haver uma resposta significativa até que você especifique qual modelo de cálculo você está usando, já que você não está limitando seu computador a comparações e trocas. Com apenas comparações de RAM e dois números, um argumento da entropia fornece um limite de tempo , mesmo para computadores transdicotômicos. Trivialmente, se em vez de trocas e comparações, a classificação é uma operação elementar, isso pode ser feito em . Se inserir um número inteiro no lugar certo for uma operação elementar, . Você tinha um modelo específico além da comparação-troca?

Ω (n \cdot l o g (n))

$\Omega(n\cdot log(n))$

Θ (1)

$\Theta(1)$

Θ (n)

$\Theta(n)$

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen Minha pergunta especifica o modelo transdicotômico de computação. Em inglês simples: um modelo de computação em que o tamanho da palavra da máquina é grande o suficiente para conter qualquer número inteiro do problema. Portanto, comparar dois números inteiros é O (1), mas adicionar, multiplicar, etc. Nesse modelo de computação, o limite entrópico já foi ultrapassado, ver Han, Yijie (2004), "Classificação determinística no tempo e espaço linear de O (n log log n)" .

orlp

@ orlp eu vejo; se você tirar proveito da estrutura dos números inteiros, poderá vencer o limite entrópico. Eu não sabia sobre classificação inteira; Certificarei-me de ler sobre esse tópico!

Lieuwe Vinkhuijzen

Respostas:

Os números inteiros podem ser classificados de forma estável em tempo com espaço adicional. $O(n)$ $O(1)$ Mais precisamente, se você tiver números inteiros no intervalo , eles podem ser classificados em O (n). $n$ $[1, n^c]$

Isso foi demonstrado apenas alguns anos atrás por uma equipe incluindo o falecido Mihai Pătrașcu (que não deveria surpreender ninguém que esteja familiarizado com seu trabalho). É um resultado notável que me surpreende que mais pessoas não conheçam, porque significa que o problema de classificar números inteiros está (teoricamente) resolvido.

Existe um algoritmo prático (fornecido no artigo acima) se você puder modificar chaves. Basicamente, você pode compactar números inteiros classificados mais do que números inteiros não classificados, e o espaço extra que você ganha é precisamente igual à memória extra necessária para fazer a classificação do radix. Eles também fornecem um algoritmo impraticável que suporta chaves somente leitura.

Pseudônimo
fonte

Pelo que entendi do resumo, isso não é geral - ele só pode classificar palavras com o tamanho

. Minha pergunta menciona explicitamente números inteiros ilimitados.

\log n

$\log n$

O (n)

$O(n)$

orlp

@orlp O terceiro algoritmo do artigo fala sobre números inteiros ilimitados.

Pseudônimo

Talvez eu esteja lendo errado, mas só consigo ver uma descrição de um método para reduzir o uso de memória de algoritmos de classificação de número ilimitado. Citando o resumo (ênfase minha): "Outra questão interessante é o caso de arbitrário . Aqui apresentamos uma transformação de caixa preta de qualquer algoritmo de classificação de RAM para um algoritmo de classificação que utiliza apenas espaço extra O (1) e tem o mesmo tempo de execução ". $c$

orlp 28/01

Perdoe-me, mas, no estado atual, essa resposta não responde à pergunta . Mencionei explicitamente que os números inteiros não são limitados . Esta resposta resolve um problema completamente diferente.

orlp

O ponto final agora não está mais em uma fonte pequena :)

orlp 29/01

-1

$O(bn)$ $b$ $n$

Se não houver limite superior no tamanho dos seus números inteiros, não acredito que exista algum algoritmo de classificação de tempo linear conhecido.

RFC 2549
fonte

Bem-vinda! O que você diz é completamente verdade, mas acho que não responde à pergunta. A pergunta pede especificamente uma prova de que o algoritmo requerido não existe em um modelo específico de computação; apenas dizer que esse algoritmo não é conhecido não prova que não exista.

David Richerby

Na verdade, b sendo uma constante em nosso problema, eu considero este algoritmo estar em O (n)

RFC 2549

b

$b$

n

$n$

O (n)

$O(n)$

o (n)

$o(n)$

Sim, definitivamente um erro de digitação;) em sua pergunta, como você supõe que um número que se encaixa em uma palavra de comprimento b, ele se torne uma constante.

RFC 2549 28/01

Isso não está tornando o tamanho das palavras uma constante. (Caso contrário, não haveria nenhuma razão para assumir explicitamente "que as operações sobre as únicas palavras levam tempo constante por operação".