Alguém está familiarizado com o algoritmo Yijie Han , espaço linear e classificação de número inteiro? Esse resultado aparece em um artigo bastante curto ( classificação determinística no tempo e no espaço linear . J. Alg. 50: 96-105, 2004), que basicamente reúne vários resultados anteriores, com adaptações. Meu problema é que ele foi escrito de uma maneira bastante ondulante, sem aprofundar-se em nenhum detalhe. Baseia-se fortemente em trabalhos anteriores, destacando-se outro artigo de Han (Classificação rápida rápida de números inteiros aprimorada no espaço linearO ( n log log n ). Information and Computation 170 (1): 81–94) escritas no mesmo estilo. Estou tendo dificuldades significativas para entender esses dois trabalhos, principalmente a maneira como eles se adaptam e usam resultados anteriores. Eu apreciaria qualquer ajuda.
É claro que isso é muito amplo e vago para ser considerado uma pergunta adequada, mas espero desenvolver uma discussão sobre várias perguntas e respostas bem definidas e focadas.
Para começar, aqui está minha primeira pergunta específica. No lema 2 das informações. Comp. Neste trabalho, existe um algoritmo de tempo recursivo para encontrar o mésimo menor número inteiro em um conjunto de números inteiros pequenos agrupados cada em palavras de RAM. A descrição do algoritmo não menciona como o caso base é tratado. Nesse caso, é necessário fazer a seleção no tempo . Como isso pode ser feito?n k k = O ( n ) O ( log k )
Respostas:
Eu estava pensando a mesma coisa.
Felizmente, consegui encontrar um artigo de jornal publicado em 2011 que explica exatamente isso; além do mais, você não precisa de uma assinatura para visualizá-la: Implementação e análise de desempenho da classificação exponencial de árvore
Eu recomendo a leitura do artigo inteiro para aprender como ele pode ser implementado e entender melhor sua teoria subjacente. Também mostra como as árvores exponenciais se comparam às árvores binárias e de classificação rápida. Aqui está o trecho relevante relacionado ao algoritmo de tempo, espaço linear e algoritmo de classificação de HanO(nloglogn) :
[6] Y. Han, classificação determinística em O (n log log n) tempo e espaço linear, 34ª STOC, 2002.
[8] A. Andersson, Classificação determinística rápida e pesquisa no espaço linear, IEEE Symposium on Foundations of Computer Science, 1996.
fonte
Não tenho certeza sobre a resposta (não passei pelo papel), mas acho que isso deve ajudar. Os números são compactados em uma única palavra; portanto, as operações em uma única palavra levam tempo O (1). Se houver, digamos, k números de h bits cada, o tamanho da palavra depende de k, h que por sua vez também depende do intervalo de números. Portanto, usamos técnicas de redução de intervalo que podem reduzir o intervalo de números para que muitos números possam caber em uma única palavra. Criando máscaras de bits apropriadas, podemos encontrar números inteiros maiores separados dos menores, considerando duas palavras por vez. Isso pode ser feito no tempo O (1). (Ontuition: para isso, cada número armazenado na palavra tem um bit de flag associado a ele e, em seguida, subtraímos duas palavras ... se o bit da flag for disparado, será um número menor).
Da mesma forma, usando acima, também podemos classificar qualquer palavra que contenha k números no tempo O (log k) (classificação bitônica).
Edit: Algoritmo para classificar 2k números no intervalo de 0 a m-1 compactados em uma palavra em que cada número tem o tamanho L de = log (m + k) +2.
Repita para t = log k para 0.
Parte 1 - separe a palavra original Z em duas palavras A e B.
Seja T obtido deslocando , (posições L-1-t) para a esquerda e ANDing o resultado com . Seja M = T- (T mudou L-1 para lugares).K2 K1
E Z com M e mude o resultado ( ) para a direita. Isso dá A.2tL
B = Z- (Z&M).
Parte 2
M = ((A OR ) -B) &K 1K1 K1
M = M- (M mudou para a esquerda L-1 lugares).
MIN = (P&B) OU (A- (A&M))
MÁX = (A&M) OU (B- (B&M))
MAX é deslocado em lugares.2tL
Finalmente, ORing MAX e MIN, retornamos Z.
Eu dei o esboço, espero que você possa preencher os detalhes necessários.
fonte