Número exato de comparações para calcular a mediana

Volume III de Knuth de The Art of Computer Programming (capítulo 5, versículo 3.2) inclui o seguinte tabela listando o exato número mínimo de comparações necessárias para selecionar o th menor elemento de um conjunto indiferenciado de tamanho , para todos . Esta tabela, juntamente com as conhecidas expressões de formulário fechado e , representa a maior parte do estado da arte em 1976 . $t$ $n$ $1\le t \le n\le 10$ $V_1(n) = n-1$ $V_2(n) = n - 2 + \lceil n/2 \rceil$

Tabela de Knuth III: 5.3.2

valor mais exato de foi calculado nos últimos 36 anos? Estou particularmente interessado nos valores exatos de , o número mínimo de comparações necessárias para calcular a mediana. $V_t(n)$ $M(n) = V_{\lceil n/2 \rceil}(n)$

Como aponta @ MarkusBläser, a tabela de Knuth parece já incorporar resultados mais recentes de Bill Gasarch, Wayne Kelly e Bill Pugh ( encontrar o i-ésimo maior de n para pequenos i, n . SIGACT News 27 (2): 88-96, 1996 .)

ds.algorithms reference-request co.combinatorics sorting selection Jeffε
fonte

O artigo mais famoso sobre o assunto, penso eu, é o de Pratt e Yao (1976), que são os primeiros a ter encontrado alguma técnica (contraditória) para provar limites inferiores sobre esse problema. Se eu encontrasse artigos recentes sobre o assunto, seguiria citações feitas neste artigo . O artigo mais recente é o de Dor e Zwick, mas há também uma pesquisa de 1996 feita por Paterson (embora eu não tenha procurado ver se ele se preocupa com resultados exatos ou não).

Jérémie

Nitpicking: Na última frase da pergunta, você provavelmente quis dizer o teto em vez do chão.

Tsuyoshi Ito

Jeff, curioso por que você está interessado na resposta exata.

Chandra Chekuri

Kenneth Oksanen escreveu um código eficiente para calcular . Infelizmente, há apenas um resumo disponível em sciencedirect.com/science/article/pii/S1571065306001582 Há dois anos, um dos meus alunos enviou um e-mail para ele e recebeu o código dele. Não me lembro se alguns novos valores poderiam ser obtidos.

V_{i} (n)

$V_i(n)$

Markus Bläser

@ChandraChekuri: Estou brincando com variantes do algoritmo de seleção em tempo linear de Blum-Floyd-Pratt-Rivest-Tarjan , como um potencial problema de dever de casa dos algoritmos. Se usarmos o algoritmo de comparação mínima para encontrar a mediana em cada bloco, qual o tamanho do bloco nos dá a melhor constante no Oh grande? 9 é melhor que 7 é melhor que 5; que tal 11?

Jeffε

Respostas:

Kenneth Oksanen publicou uma tabela expandida de valores até , com base em sua própria pesquisa no computador . Okansen também fornece descrições das árvores de comparação ideais para a maioria dos valores que ele relata. Aqui está uma captura de tela de sua tabela: $n=15$

Os limites de Kenneth Oksanen para a seleção

Obrigado a @ MarkusBläser pela liderança!

Jeffε
fonte

Gostaria de saber se essa informação pode ser útil para você. Infelizmente, ele não fornece nenhuma informação adicional para a pergunta desta publicação, mas é mais uma resposta ao seu comentário sobre o que era isso (analisando variantes do QuickSelect).

O número mínimo esperado de comparações, observado ou é obviamente significativamente mais fácil de calcular (com a expectativa tomada uniformemente em todas as permutações), $v(n,t)$ $v_t(n)$

v_{t} (n) = n + min (t, n - t) + l.o.t. .

$v_t(n)=n+\min(t,n-t)+\text{l.o.t.}.$

Esse resultado não é usado com pouca frequência e, em particular, é a base para os algoritmos em "Amostra adaptável para o QuickSelect" de Martínez, Panario e Viola . O ponto de partida do trabalho é a mediana de três em QuickSelect e, depois, perguntar: é pertinente escolher sistematicamente a mediana, quando o elemento que procuramos tem uma classificação relativa muito menor que n / 2 ou muito maior que n / 2 ?

Em outras palavras, suponha que você esteja procurando o ésimo elemento em uma lista de elementos e esteja escolhendo seu pivô entre os clusters de elementos. Em vez de tomar a mediana ( ), você levará onde . Eles mostram que esse algoritmo pode, para a escolha certa de ser praticamente mais eficiente que a variante mediana de três. $k$ $n$ $m$ $m/2$ $\alpha m$ $\alpha = k/n$ $m$

Jérémie
fonte