Limite inferior teórico de encontrar o número de ocorrências de um inteiro de destino em uma matriz ordenada

Question

.

Dada uma matriz ordenada de inteiros e um inteiro de destino, encontre o número de ocorrências do inteiro de destino.

É bem conhecido que uma busca binária tem complexidade de tempo $ O (\ lg n) $ onde $ n$ é o tamanho da matriz. Por exemplo, dado uma matriz $ [1,2,3,3,4,5] $ e um alvo $ 3,$ O algoritmo deve retornar $ 2 $ desde que existem duas cópias da $ 3 $ na matriz.

.

Pergunta: Existe um algoritmo mais rápido que tem complexidade de tempo menor que $ O (\ lg n)? $ Caso contrário, há uma prova para provar que $ \ ômega (\ lg n) $ é o limite inferior teórico?

Answer 1

O problema requer $ \ ômega (\ log n) $ Acessa à memória, mesmo se você é prometido que o inteiro de destino aparece no máximo uma vez. Você pode provar isso usando um argumento adversário.

Diga que o alvo é zero. Se o primeiro acesso à matriz é deixado de centro, responda $ - 1 $ e estabelecer mentalmente os elementos à esquerda para serem $ - 2, -3, \ ldots $ . Se o primeiro acesso estiver à direita do centro, responda $ + 1 $ e estabelecer mentalmente os elementos à direita para ser $ 2 , 3, \ ldots $ .

Suponha que o primeiro acesso tenha sido à direita do centro, digamos posição $ i $ e considere o segundo acesso. Se à direita do primeiro acesso, então você já sabe o que responder. Caso contrário, existem dois casos. Se a posição acessada $ J $ é menor que $ i / 2 $ , responda $ - 1 $ (e preencha elementos à esquerda). Se fosse mais do que $ i / 2 $ , responda $ + 1/2 $ (e preencha elementos à direita para posicionar $ i $ ).

Continuando desta forma, em cada etapa o número de posições que podem conter o elemento-alvo é no máximo metade em cada etapa. Finalmente, quando apenas um elemento ainda está em jogo, sem consultar, o algoritmo não pode saber com certeza se a matriz contém o elemento-alvo ou não. É preciso $ \ log_2 n $ etapas para chegar a esta etapa.

O precedente, na verdade, mostra que a pesquisa binária é ideal para pesquisar uma matriz classificada.

Answer 2

Existem $ n $ possíveis respostas.Cada comparação lhe dá no máximo um pouco de informação.Você precisa pelo menos $ \ lg n $ bits de informação para descrever a resposta, para que você precise pelo menos $ \LG N $ Comparações.