Algoritmo de seleção - Selection algorithm

Em ciência da computação , um algoritmo de seleção é um algoritmo para encontrar o k- ésimo menor número em uma lista ou array ; um tal número é chamado o k th ordem estatística . Isso inclui os casos de encontrar os elementos mínimo , máximo e mediano . Existem algoritmos de seleção de tempo O ( n ) (tempo linear de pior caso) e o desempenho sublinear é possível para dados estruturados; no extremo, O (1) para uma matriz de dados classificados. A seleção é um subproblema de problemas mais complexos, como o vizinho mais próximo e os problemas do caminho mais curto . Muitos algoritmos de seleção são derivados generalizando um algoritmo de classificação e, inversamente, alguns algoritmos de classificação podem ser derivados como aplicação repetida de seleção.

O caso mais simples de um algoritmo de seleção é encontrar o elemento mínimo (ou máximo) iterando pela lista, mantendo o controle do mínimo em execução - o mínimo até agora - (ou máximo) e pode ser visto como relacionado à classificação da seleção . Por outro lado, o caso mais difícil de um algoritmo de seleção é encontrar a mediana. Na verdade, um algoritmo de seleção de mediana especializado pode ser usado para construir um algoritmo de seleção geral, como na mediana das medianas . O algoritmo de seleção mais conhecido é Quickselect , que está relacionado ao Quicksort ; como Quicksort, ele tem (assintoticamente) desempenho médio ideal, mas desempenho de pior caso ruim, embora possa ser modificado para fornecer desempenho de pior caso ideal também.

Seleção por ordenação

Ao classificar a lista ou matriz e, em seguida, selecionar o elemento desejado, a seleção pode ser reduzida à classificação . Este método é ineficiente para selecionar um único elemento, mas é eficiente quando muitas seleções precisam ser feitas a partir de uma matriz, caso em que apenas uma classificação inicial e cara é necessária, seguida por muitas operações de seleção baratas - O (1) para uma matriz , embora a seleção seja O ( n ) em uma lista encadeada, mesmo se classificada, devido à falta de acesso aleatório . Em geral, a classificação requer tempo O ( n log n ), onde n é o comprimento da lista, embora um limite inferior seja possível com algoritmos de classificação não comparativos como classificação por raiz e classificação por contagem .

Em vez de classificar toda a lista ou array, pode-se usar a classificação parcial para selecionar os k menores ou k maiores elementos. O k- ésimo menor (resp., K- ésimo maior elemento) é então o maior (resp., O menor elemento) da lista parcialmente classificada - isso então leva O (1) para acessar em uma matriz e O ( k ) para acessar em uma lista.

Classificação parcial não ordenada

Se a classificação parcial for relaxada para que os k menores elementos sejam retornados, mas não em ordem, o fator de O ( k log k ) pode ser eliminado. Uma seleção máxima adicional (levando tempo O ( k )) é necessária, mas desde então , isso ainda produz complexidade assintótica de O ( n ). Na verdade, os algoritmos de seleção baseados em partição produzem o k- ésimo menor elemento em si e os k- menores elementos (com outros elementos não em ordem). Isso pode ser feito em tempo O ( n ) - complexidade média de Quickselect e complexidade de pior caso de algoritmos de seleção baseados em partição refinados. ${\ displaystyle k \ leq n}$

Por outro lado, dado um algoritmo de seleção, pode-se facilmente obter uma classificação parcial não ordenada ( k menores elementos, não em ordem) em tempo O ( n ) iterando através da lista e gravando todos os elementos menores que o k- ésimo elemento. Se isso resultar em menos de k  - 1 elementos, quaisquer elementos restantes serão iguais ao k- ésimo elemento. Cuidados devem ser tomados, devido à possibilidade de igualdade de elementos: não se deve incluir todos os elementos menos do que ou igual a do k -ésimo elemento, como elementos superiores ao k th elemento pode também ser igual a ele.

Assim, a classificação parcial não ordenada (os k elementos mais baixos , mas não ordenados) e a seleção do k- ésimo elemento são problemas muito semelhantes. Não apenas eles têm a mesma complexidade assintótica, O ( n ), mas uma solução para qualquer um pode ser convertida em uma solução para o outro por um algoritmo direto (encontrando um máximo de k elementos ou filtrando elementos de uma lista abaixo de um corte do valor do k- ésimo elemento).

Classificação parcial da seleção

Um exemplo simples de seleção por classificação parcial é usar a classificação por seleção parcial .

O algoritmo de tempo linear óbvio para encontrar o mínimo (resp. Máximo) - iterando sobre a lista e mantendo o controle do elemento mínimo (resp. Máximo) até agora - pode ser visto como uma classificação de seleção parcial que seleciona o 1 menor elemento. No entanto, muitas outras classificações parciais também se reduzem a esse algoritmo para o caso k = 1, como uma classificação de heap parcial.

Mais geralmente, uma classificação de seleção parcial produz um algoritmo de seleção simples que leva tempo O ( kn ). Isso é assintoticamente ineficiente, mas pode ser suficientemente eficiente se k for pequeno e fácil de implementar. Concretamente, simplesmente encontramos o valor mínimo e o movemos para o início, repetindo na lista restante até que tenhamos acumulado k elementos, e então retornamos o k- ésimo elemento. Aqui está o algoritmo baseado em classificação de seleção parcial:

function select(list[1..n], k)
    for i from 1 to k
        minIndex = i
        minValue = list[i]
        for j from i+1 to n do
            if list[j] < minValue then
                minIndex = j
                minValue = list[j]
        swap list[i] and list[minIndex]
    return list[k]

Seleção baseada em partição

O desempenho linear pode ser alcançado por um algoritmo de seleção baseado em partição, mais basicamente Quickselect . Quickselect é uma variante do Quicksort - em ambos escolhe um pivô e então particiona os dados por ele, mas enquanto o Quicksort recorre em ambos os lados da partição, Quickselect recorre apenas em um lado, ou seja, o lado em que o k- ésimo elemento desejado está . Como com Quicksort, este tem desempenho médio ideal, neste caso linear, mas desempenho de pior caso ruim, neste caso quadrático. Isso ocorre, por exemplo, tomando o primeiro elemento como o pivô e procurando o elemento máximo, se os dados já estiverem classificados. Na prática, isso pode ser evitado escolhendo um elemento aleatório como pivô, o que produz um desempenho quase linear certo . Alternativamente, uma estratégia de pivô determinística mais cuidadosa pode ser usada, como mediana de medianas . Eles são combinados no algoritmo híbrido introselect (análogo ao introsort ), que começa com Quickselect, mas retorna à mediana das medianas se o progresso for lento, resultando em desempenho médio rápido e desempenho de pior caso ideal de O ( n ).

Os algoritmos baseados em partição geralmente são feitos no local, o que resulta na classificação parcial dos dados. Eles podem ser feitos fora do lugar, sem alterar os dados originais, ao custo de O ( n ) espaço adicional.

Seleção mediana como estratégia pivô

Um algoritmo de seleção de mediana pode ser usado para produzir um algoritmo de seleção geral ou algoritmo de classificação, aplicando-o como a estratégia de pivô no Quickselect ou Quicksort; se o algoritmo de seleção de mediana for assintoticamente ótimo (tempo linear), a seleção resultante ou o algoritmo de classificação também o serão. Na verdade, uma mediana exata não é necessária - uma mediana aproximada é suficiente. No algoritmo de seleção de mediana de medianas , a estratégia de pivô calcula uma mediana aproximada e a usa como pivô, recorrendo em um conjunto menor para calcular esse pivô. Na prática, a sobrecarga da computação dinâmica é significativa, então esses algoritmos geralmente não são usados, mas essa técnica é de interesse teórico para relacionar algoritmos de seleção e classificação.

Em detalhe, dado um algoritmo de seleção de mediana, pode-se usá-lo como estratégia de pivô no Quickselect, obtendo um algoritmo de seleção. Se o algoritmo de seleção de mediana é ótimo, significando O ( n ), então o algoritmo de seleção geral resultante também é ótimo, novamente significando linear. Isso ocorre porque Quickselect é um algoritmo de divisão e conquista , e usar a mediana em cada pivô significa que em cada etapa o conjunto de pesquisa diminui pela metade do tamanho, então a complexidade geral é uma série geométrica vezes a complexidade de cada etapa e, portanto, simplesmente uma constante vezes a complexidade de uma única etapa, na verdade vezes (somando as séries). ${\ displaystyle 2 = 1 / (1- (1/2))}$

Da mesma forma, dado um algoritmo de seleção de mediana ou algoritmo de seleção geral aplicado para encontrar a mediana, pode-se usá-lo como uma estratégia de pivô no Quicksort, obtendo um algoritmo de classificação. Se o algoritmo de seleção for ótimo, significando O ( n ), então o algoritmo de classificação resultante é ótimo, significando O ( n log n ). A mediana é o melhor pivô para classificação, pois divide os dados uniformemente e, portanto, garante classificação ideal, assumindo que o algoritmo de seleção seja ideal. Existe um análogo de classificação à mediana das medianas, usando a estratégia de pivô (mediana aproximada) no Quicksort e, da mesma forma, produz um Quicksort ideal.

Ordenação incremental por seleção

Converta a seleção por classificação, pode-se classificar de forma incremental por seleção repetida. Abstratamente, a seleção produz apenas um único elemento, o k ésimo elemento. No entanto, algoritmos de seleção prática frequentemente envolvem classificação parcial ou podem ser modificados para isso. Selecionar por classificação parcial naturalmente faz isso, classificando os elementos até k , e selecionando por particionamento também classifica alguns elementos: os pivôs são classificados nas posições corretas, com o k- ésimo elemento sendo o pivô final, e os elementos entre os pivôs têm valores entre os valores dinâmicos. A diferença entre seleção baseada em partição e classificação baseada em partição, como em Quickselect versus Quicksort, é que na seleção um recorre em apenas um lado de cada pivô, classificando apenas os pivôs (uma média de log ( n ) pivôs são usados), em vez de repetir em ambos os lados do pivô.

Isso pode ser usado para acelerar as seleções subsequentes nos mesmos dados; no extremo, uma matriz totalmente classificada permite a seleção O (1). Além disso, em comparação com fazer primeiro uma classificação completa, a classificação incremental por seleção repetida amortiza o custo de classificação nas seleções múltiplas.

Para dados parcialmente classificados (até k ), desde que os dados parcialmente classificados e o índice k até o qual os dados são classificados sejam registrados, as seleções subsequentes de j menor ou igual a k podem simplesmente selecionar o j- ésimo elemento, como ele já está classificado, enquanto as seleções de j maiores que k precisam apenas classificar os elementos acima da k- ésima posição.

Para dados particionados, se a lista de pivôs for armazenada (por exemplo, em uma lista classificada dos índices), então as seleções subsequentes só precisam selecionar o intervalo entre dois pivôs (os pivôs mais próximos abaixo e acima). O maior ganho vem dos pivôs de nível superior, que eliminam grandes partições caras: um único pivô próximo ao meio dos dados reduz pela metade o tempo para seleções futuras. A lista dinâmica crescerá com as seleções subsequentes, à medida que os dados se tornam mais classificados e podem até mesmo ser passados ​​para uma classificação baseada em partição como base para uma classificação completa.

Usando estruturas de dados para selecionar em tempo sublinear

Dada uma lista desorganizada de dados, o tempo linear (Ω ( n )) é necessário para encontrar o elemento mínimo, porque temos que examinar cada elemento (caso contrário, podemos perdê-lo). Se organizarmos a lista, por exemplo, mantendo-a sempre ordenada, então selecionar o k- ésimo maior elemento é trivial, mas a inserção requer tempo linear, como fazem outras operações, como combinar duas listas.

A estratégia para encontrar uma estatística de pedido no tempo sublinear é armazenar os dados de forma organizada usando estruturas de dados adequadas que facilitam a seleção. Duas dessas estruturas de dados são estruturas baseadas em árvore e tabelas de frequência.

Quando apenas o mínimo (ou máximo) é necessário, uma boa abordagem é usar um heap , que é capaz de encontrar o elemento mínimo (ou máximo) em tempo constante, enquanto todas as outras operações, incluindo a inserção, são O (log n ) ou melhor. De maneira mais geral, uma árvore de busca binária de autobalanceamento pode ser facilmente aumentada para tornar possível inserir um elemento e encontrar o k- ésimo maior elemento no tempo O (log n ); isso é chamado de árvore de estatística do pedido . Simplesmente armazenamos em cada nó uma contagem de quantos descendentes ele possui e usamos isso para determinar qual caminho seguir. As informações podem ser atualizadas de forma eficiente, pois a adição de um nó afeta apenas a contagem de seus ancestrais O (log n ), e as rotações da árvore afetam apenas a contagem dos nós envolvidos na rotação.

Outra estratégia simples é baseada em alguns dos mesmos conceitos da tabela hash . Quando conhecemos o intervalo de valores de antemão, podemos dividir esse intervalo em h subintervalos e atribuí-los a h intervalos . Quando inserimos um elemento, nós o adicionamos ao intervalo correspondente ao intervalo em que ele se enquadra. Para encontrar o elemento mínimo ou máximo, varremos desde o início ou fim o primeiro intervalo não vazio e encontramos o elemento mínimo ou máximo nesse intervalo . Em geral, para encontrar o k- ésimo elemento, mantemos uma contagem do número de elementos em cada intervalo, em seguida, examinamos os intervalos da esquerda para a direita somando contagens até encontrarmos o intervalo contendo o elemento desejado e, em seguida, usamos a linha linear esperada algoritmo de tempo para encontrar o elemento correto nesse intervalo.

Se escolhermos h de tamanho aproximadamente sqrt ( n ), e a entrada estiver quase uniformemente distribuída, este esquema pode realizar seleções no tempo O (sqrt ( n )) esperado . Infelizmente, essa estratégia também é sensível ao agrupamento de elementos em um intervalo estreito, o que pode resultar em intervalos com um grande número de elementos (o agrupamento pode ser eliminado por meio de uma boa função hash, mas encontrar o elemento com o k ésimo maior valor hash isn ' t muito útil). Além disso, como as tabelas de hash, essa estrutura requer redimensionamentos da tabela para manter a eficiência conforme os elementos são adicionados e n se torna muito maior do que h ² . Um caso útil disso é encontrar uma estatística de pedido ou extremo em um intervalo finito de dados. Usar a tabela acima com intervalo de intervalo 1 e manter contagens em cada intervalo é muito superior a outros métodos. Essas tabelas hash são como tabelas de frequência usadas para classificar os dados em estatísticas descritivas .

Limites inferiores

Em The Art of Computer Programming , Donald E. Knuth discutiu uma série de limites inferiores para o número de comparações necessárias para localizar as t menores entradas de uma lista desorganizada de n itens (usando apenas comparações). Existe um limite inferior trivial de n - 1 para a entrada mínima ou máxima. Para ver isso, considere um torneio onde cada jogo representa uma comparação. Como todos os jogadores, exceto o vencedor do torneio, devem perder um jogo antes de sabermos o vencedor, temos um limite inferior de n - 1 comparações.

A história se torna mais complexa para outros índices. Definimos como o número mínimo de comparações necessárias para encontrar os menores valores de t . Knuth faz referência a um artigo publicado por SS Kislitsyn, que mostra um limite superior para este valor: ${\ displaystyle W_ {t} (n)}$

${\ displaystyle W_ {t} (n) \ leq n-t + \ sum _ {n + 1-t <j \ leq n} \ lceil {\ log _ {2} \, j} \ rceil \ quad {\ text {para}} \, n \ geq t}$

Este limite é alcançável para t = 2, mas melhor, limites mais complexos são conhecidos para t maior .

Complexidade do espaço

A complexidade de espaço necessária de seleção é O (1) armazenamento adicional, além de armazenar a matriz na qual a seleção está sendo realizada. Essa complexidade de espaço pode ser alcançada preservando a complexidade de tempo O (n) ideal.

Algoritmo de seleção online

A seleção online pode referir-se estritamente ao cálculo do k- ésimo menor elemento de um fluxo, caso em que algoritmos de classificação parcial - com espaço k + O (1) para os k menores elementos até agora - podem ser usados, mas algoritmos baseados em partição não podem ser .

Alternativamente, a própria seleção pode ser obrigada a estar online , ou seja, um elemento só pode ser selecionado a partir de uma entrada sequencial na instância de observação e cada seleção, respectivamente recusa, é irrevogável. O problema é selecionar, sob essas restrições, um elemento específico da sequência de entrada (como por exemplo o maior ou o menor valor) com maior probabilidade. Este problema pode ser resolvido pelo algoritmo de Odds , que produz o ótimo sob uma condição de independência; ele também é ótimo como um algoritmo com o número de cálculos sendo linear no comprimento da entrada.

O exemplo mais simples é o problema da secretária de escolher o máximo com alta probabilidade, caso em que a estratégia ótima (em dados aleatórios) é rastrear o máximo em execução dos primeiros n / e elementos e rejeitá-los e, em seguida, selecionar o primeiro elemento que é superior a este máximo.

Problemas relacionados

Pode-se generalizar o problema de seleção para aplicar a intervalos dentro de uma lista, resultando no problema de consultas de intervalo . A questão das consultas de medianas de intervalo (computando as medianas de vários intervalos) foi analisada.

Suporte de linguas

Muito poucos idiomas têm suporte integrado para seleção geral, embora muitos forneçam recursos para localizar o menor ou o maior elemento de uma lista. Uma excepção notável é C ++ , o qual fornece um modelada nth_elementmétodo com uma garantia de tempo linear esperado, e também partições os dados, o que requer que o n ésimo elemento ser classificados em seu lugar correcto, elementos antes do N -ésimo elemento são menos do que, e elementos após o n ésimo elemento são maiores do que isso. É implícito, mas não exigido, que ele é baseado no algoritmo de Hoare (ou alguma variante) por seu requisito de tempo linear esperado e particionamento de dados.

Para Perl , o módulo Sort :: Key :: Top , disponível no CPAN , fornece um conjunto de funções para selecionar os n elementos principais de uma lista usando vários ordenamentos e procedimentos de extração de chave personalizados. Além disso, o módulo Statistics :: CaseResampling fornece uma função para calcular quantis usando Quickselect.

A biblioteca padrão do Python (desde 2.4) inclui heapq.nsmallest()e nlargest(), retornando listas ordenadas, em tempo O ( n log k ).

O Matlab inclui funções maxk()e mink(), que retornam os valores máximos (mínimos) de k em um vetor, bem como seus índices.

Como o suporte ao idioma para classificação é mais onipresente, a abordagem simplista de classificação seguida pela indexação é preferida em muitos ambientes, apesar de sua desvantagem na velocidade. De fato, para linguagens preguiçosas , esta abordagem simplista pode até atingir a melhor complexidade possível para o k menor / maior classificado (com máximo / mínimo como um caso especial) se a classificação for preguiçosa o suficiente.

Veja também

• Otimização ordinal

Referências

links externos

• " Lecture notes for January 25, 1996: Selection and order statistics ", ICS 161: Design and Analysis of Algorithms, David Eppstein