"Quase classificando" números inteiros em tempo linear

Estou interessado em classificar uma matriz de valores inteiros positivos $L = v_1, \ldots, v_n$ em tempo linear (no modelo de RAM com medida de custo uniforme, ou seja, números inteiros podem ter tamanho logarítmico, mas presume-se que as operações aritméticas nelas tempo da unidade). Obviamente, isso é impossível com algoritmos de classificação baseados em comparação, por isso estou interessado em calcular uma classificação "aproximada", isto é, calcular alguma permutação de que não é realmente classificado em geral, mas uma "boa aproximação" da versão classificada de$v_{\sigma(1)}, \ldots, v_{\sigma(n)}$$L$$L$. Suponho que estamos ordenando os números inteiros em ordem decrescente, pois isso torna a sequência um pouco mais agradável de declarar, mas é claro que se poderia dizer o problema da outra maneira.

Um critério possível para uma classificação aproximada é o seguinte (*): deixando ser , para cada , exigimos que (ou seja, a lista "quase ordenada" é delimitada de cima pela função decrescente ). É fácil ver que a classificação real satisfaz isso: deve ser maior que portanto, é no máximo que é e, em geral, deve ser maior que que é$N$$\sum_i v_i$$1 \leq i \leq n$$v_{\sigma(i)} \leq N/i$$i \mapsto N/i$$v_{\sigma(2)}$$v_{\sigma(1)}$$(v_{\sigma(1)} + v_{\sigma(2)})/2$$\leq N/2$$v_{\sigma(i)}$$(\sum_{j \leq i} v_{\sigma(i)})/i$$\leq N/i$.

Por exemplo, o requisito (*) pode ser alcançado pelo algoritmo abaixo (sugerido por @Louis). Minha pergunta é: Existe trabalho existente nessa tarefa de "quase classificar" números inteiros em tempo linear, impondo algum requisito como (*) que a classificação real satisfaria? O algoritmo abaixo, ou alguma variante dele, tem um nome estabelecido?

Edit: corrigido o algoritmo e adicionado mais explicações

Algoritmo:

INPUT: V an array of size n containing positive integers
OUTPUT: T

N = Σ_{i<n} V[i]
Create n buckets indexed by 1..n
For i in 1..n
| Add V[i] into the bucket min(floor(N/V[i]),n)
+

For bucket 1 to bucket n
| For each element in the bucket
| | Append element to T
| +
+

Esse algoritmo funciona conforme planejado pelos seguintes motivos:

1. Se um elemento $v$ estiver no balde $j$ então $v ≤ N/j$ .

   $v$$j=\min(N/v,n)$$j ≤ \lfloor N/v\rfloor ≤ N/v$

2. Se um elemento estiver no intervalo então ou . $v$$j$$N/(j+1) < v$$j=n$

   $v$j = min ( N / v , n ) j = ⌊ N / v ⌋ j = n j = ⌊ N / v ⌋ j ≤ N / v < j + 1 N / ( j + 1 ) < v é colocado no balde , assim ou . No primeiro caso, que significa e, portanto, .$j=\min(N/v,n)$$j = \lfloor N/v \rfloor$$j=n$$j=\lfloor N/v\rfloor$$j ≤ N/v < j+1$$N/(j+1) < v$

3. Para , existem, no máximo, elementos nos buckets de 1 a .$j<n$$j$$j$

   Seja e seja o número total de elementos em um dos blocos 1..j. Por 2. temos que todo elemento em um balde (com ) é tal que . Portanto, a soma de todos os elementos nos buckets de a é maior que . Mas essa soma também é menor que portanto, e, portanto, que nos dá ou .$j<n$$k$v i i ≤ j N / ( j + 1 ) ≤ N / ( i + 1 ) < v K 1 j k × N / ( J + 1 ) K N k × N / ( j + 1 ) < K ≤ N k / ( j + 1 ) 1$v$$i$$i ≤ j$$N/(j+1)≤N/(i+1)<v$$K$$1$$j$$k×N/(J+1)$$K$$N$$k×N/(j+1) < K ≤ N$$k/(j+1) < 1$$k<j+1$$k≤j$

4. $T$ satisfaz (*) ou seja, o ésimo elemento de é tal que$j$$T$$T[j] ≤ N/j$

   Por 3. temos que , o ésimo elemento de , vem de um balde com portanto .$T[j]$$j$$T$$i$$i ≥ j$$T[j] ≤ N/i ≤ N/j$

5. Esse algoritmo leva tempo linear.

   A computação de leva tempo linear. Os buckets podem ser implementados com uma lista vinculada que possui inserção e iteração . O loop aninhado é executado quantas vezes houver elementos (ou seja, vezes).$N$$O(1)$$n$

Isso parece muito com o algoritmo ASort. Veja este artigo de Giesen et. al .:

https://www.inf.ethz.ch/personal/smilos/asort3.pdf

Infelizmente, o tempo de execução não é linear. O artigo acima prova que qualquer algoritmo aleatório à base de comparação Classificação itens dentro de N 2 / ν ( n ) tem um limite inferior de N * l o g ( ν ( n ) ) (assumindo ν ( n ) < n ).$n$$n^2/\nu(n)$$n*log (\nu(n))$$\nu(n) < n$

EDIT , em resposta aos esclarecimentos da pergunta:

O que você está fazendo é simplesmente uma espécie de balde . No entanto, o algoritmo para classificação de buckets não é linear nesse caso. O problema: você precisa somar os números naturais e, em seguida, realizar a divisão em cada um deles. Como os números são ilimitados em tamanho, não é mais uma operação de tempo constante. Levará mais tempo para realizar o maior número de números que você precisa somar.$N/V[i]$

Quanto tempo mais? A divisão depende do número de dígitos; portanto, é , vezes n operações de divisão. Provavelmente isso parece familiar. :)$lg(n)$$n$

Afinal, minha pergunta é bastante irrelevante, afinal. Na verdade, estou trabalhando na máquina de RAM com uma medida de custo uniforme (ou seja, temos registradores cujos registros não são necessariamente de tamanho constante, mas podemos armazenar números inteiros de tamanho logarítmico na entrada, no máximo, e as operações nesses registradores levam tempo constante, incluindo pelo menos adição). E, de fato, neste modelo, a classificação de números inteiros (executando essencialmente uma classificação de raiz) pode ser feita em tempo linear. Isso é explicado no artigo de 1996 por Grandjean, Sorting, tempo linear e o problema de satisfação .

(Isso não responde à minha pergunta sobre se existem noções bem estudadas de "quase classificar" um conjunto de números inteiros, mas, para que sejam interessantes, provavelmente seria necessário que essas noções mais fracas fossem mais fáceis de aplicar, ou seja, trabalhe em uma mais fraca modelo ou de alguma forma executado no tempo sublinear. No entanto, atualmente não estou ciente de um sentido em que esse seria o caso.)