Complexidade assintótica da classificação usando comparações k

A classificação usando comparações de dois elementos tem uma complexidade assintótica de pior caso de (alcançada por mergesort, heapsort, inserção binária, ford-johnson, pelo menos), o que é ideal.$n \log_2(n)$

Se classificarmos usando comparações que classificam k elementos como blocos de construção, o limite inferior da teoria da informação é . Podemos facilmente alcançar com a inserção do k-ário.n log k ( n $n \log_{k!}(n)$$n \log_k(n)$

Pergunta: Onde está a complexidade ideal entre e ?n log k ! ( N $n \log_k(n)$$n \log_{k!}(n)$

Refs apropriados também seriam apreciados.

Edit: porque não estava claro:

Estou interessado na complexidade em , com . Possui o comportamento assintótico de com Ei gostaria de mais precisão sobre .k = O ( 1 ) α n log 2 ( n ) α ∈ [ $n$$k=O(1)$$\alpha n\log_2(n)$$\alpha \in [\frac{1}{\log_2(k)},\frac{1}{\log_2(k!)}]$$\alpha$

Como me disseram Abhishek Methuku, isso já foi estudado, de fato várias vezes, veja, por exemplo, http://www.researchgate.net/publication/3042594_Sorting_n_objects_with_a_k-sorter

Para large, a resposta está próxima de mas, por exemplo, parece estar aberto.n log k ! ( n ) k = $k$$n \log_{k!}(n)$$k=3$

Primeiro, vamos trazer aqueles para o que eu acho que é a forma correta de se olhar.


$\Theta\left(n\cdot \log_k(n)\right) \: = \: \Theta\left(n\cdot \frac{\log_2(n)}{\log_2(k)}\right) \: = \: \Theta\left(\frac{n\cdot \log_2(n)}{\log_2(k)}\right)$

e

$\Theta\left(n\cdot \log_{k!}(n)\right) \: = \: \Theta\left(n\cdot \frac{\log_2(n)}{\log_2(k!)}\right) \: = \: \Theta\left(\frac{n\cdot \log_2(n)}{k\cdot \log_2(k)}\right)$

Observe que uma comparação -ary é suficiente para comparações simultâneas (binárias).$k$$\: \left\lfloor \frac{k}2 \right\rfloor \:$

Para ,.$\: 2\leq k \:$$\:$ $\;\; \left\lfloor \frac{k}2 \right\rfloor \: \in \: \Theta(k) \;\;$

Pela rede AKS , para , comparações são suficientes para -ary ordenar.$\: 2\leq k\leq O(n) \:$$\:$ $O\left(\frac{n\cdot \log_2(n)}k\right)$ $k$

Quando , comparação -ary é suficiente para classificar. $\: n\leq k \:$$\:$ $1 \:\: k$$\quad$ $1\in O\left(\frac{n\cdot \log_2(n)}k\right)$

Portanto, para , comparações -ary são suficientes para classificar.$\: 2\leq k \:$$\:$ $O\left(\frac{n\cdot \log_2(n)}k\right)$ $k$

$5$ $k$ comparações -ary são suficientes para um -ary comparação.$\: \left(4\cdot \left\lfloor \frac{k}2 \right\rfloor \right)$$\:$

Para , comparações -ary são suficientes para uma$\: 4\leq k \:$$\:$ $5\:\:k$-arycomparação.$\: \left(\frac32 \cdot k\right)$$\:$

Para , .$\: 2\leq k\leq n \:$$\:$ $\log_{\frac32}\left(\frac{n}k\right) = \frac{\log_2\left(\frac{n}k\right)}{\log_2\left(\frac32\right)} \:$

Para , comparações ar são suficientes para classificar.$\: 2\leq k\leq n \:$$\:$ $5^{\left\lceil \frac{\log_2\left(\frac{n}k\right)}{\log_2\left(\frac32\right)} \right\rceil}$ $k$

Para , pelo menos um comparação -ary é necessário para classificar.$\: 2\leq n \:$$\:$$k$

Portanto, para e , triagem leva exactamente comparações -ary.$\: 2\leq k\leq n \:$$\: \frac{n}k \in O(1) \:$$\:$$\Theta(1)$ $k$

Suspeito que alguém possa refinar a segunda das minhas duas
conclusões para mostrar que seu limite inferior é alcançado.