Deixe-me esclarecer:

Dado um gráfico de dispersão de um determinado número de pontos n, se eu quiser encontrar o ponto mais próximo de qualquer ponto do gráfico mentalmente, posso imediatamente ignorar a maioria dos pontos no gráfico, restringindo minhas escolhas a um número pequeno e constante de pontos próximos .

No entanto, na programação, dado um conjunto de pontos n, para encontrar o ponto mais próximo de qualquer um, é necessário verificar todos os outros pontos, que são .${\cal O}(n)$

Suponho que a visão visual de um gráfico seja provavelmente o equivalente a alguma estrutura de dados que sou incapaz de entender; porque com a programação, convertendo os pontos em um método mais estruturado, como um quadtree, é possível encontrar os pontos mais próximos de pontos em no tempo ou com a amortização tempo.n k ⋅ log ( n ) O ( log n $k$$n$$k\cdot\log(n)$${\cal O}(\log n)$

Mas ainda não existem algoritmos amortizados (que eu possa encontrar) para encontrar pontos após a reestruturação dos dados.${\cal O}(1)$

Então, por que isso parece possível com mera inspeção visual?

Seu modelo do que você faz mentalmente está incorreto. De fato, você opera em duas etapas:

1. Elimine todos os pontos que estão longe demais, no tempo .$O(1)$
2. Meça os pontos mais próximos, em .Θ ( m $m$$\Theta(m)$

Se você jogou jogos como petanca ou boliche, isso deve ser familiar - você não precisa examinar os objetos que estão muito longe do alvo, mas pode ser necessário medir os candidatos mais próximos.

Para ilustrar esse ponto, qual ponto verde está mais próximo do ponto vermelho? (Apenas com pouco mais de 1 pixel, mas há um mais próximo.) Para facilitar as coisas, os pontos foram codificados por distância.

Esta figura contém pontos que estão quase em círculo e pontos verdes no total. A etapa 1 permite eliminar todos os pontos, exceto , mas a etapa 2 exige a verificação de cada um dos pontos. Não há limite a priori para .n ≫ 10 m m $m=10$$n \gg 10$$m$$m$$m$

Uma observação física permite reduzir o tamanho do problema de todo o conjunto de pontos para um conjunto restrito de candidatos de pontos. Esta etapa não é uma etapa de computação, como é comumente entendida, porque é baseada em um processo contínuo. Os processos contínuos não estão sujeitos às intuições usuais sobre complexidade computacional e, em particular, à análise assintótica.$n$$m$

Agora, você pode perguntar: por que um processo contínuo não pode resolver completamente o problema? Como chega a esses pontos, por que não podemos refinar o processo para obter ?m = $m$$m=1$

A resposta é que eu trapacei um pouco: apresentei um conjunto de pontos que é gerado para consistir em pontos quase mais próximos e pontos que são mais adiante. Em geral, determinar quais pontos se encontram dentro de um limite preciso requer uma observação precisa que deve ser realizada ponto a ponto. Um processo grosseiro de eliminação permite excluir muitos não candidatos óbvios, mas apenas decidir quais candidatos restam exige enumerá-los.n - $m$$n-m$

Você pode modelar esse sistema em um mundo computacional discreto. Suponha que os pontos sejam representados em uma estrutura de dados que os classifique em células em uma grade, ou seja, o ponto é armazenado em uma lista da célula . Se você estiver procurando os pontos mais próximos e a célula que contém esse ponto contiver no máximo um outro ponto, será suficiente verificar a célula que contém as 8 células vizinhas. O número total de pontos nessas 9 células é . Este modelo respeita algumas propriedades principais do modelo humano:( ⌊ x ⌋ , ⌊ y ⌋ ) ( x 0 , y 0 ) $(x,y)$$(\lfloor x \rfloor, \lfloor y \rfloor)$$(x_0, y_0)$$m$

• $m$ é potencialmente ilimitado - sempre é possível um pior caso degenerado de, por exemplo, pontos próximos a um círculo.
• A eficiência prática depende da seleção de uma escala que corresponda aos dados (por exemplo, você não economizará nada se seus pontos estiverem em um pedaço de papel e suas células tiverem 1 km de largura).

O motivo é que os dados foram colocados em uma "estrutura de dados" otimizada para esta consulta e que o tempo de pré-processamento na preparação do gráfico deve ser incluído nos tempos medidos, proporcional ao número de pontos, fornecendo O (n) complexidade ali.

Se você colocar as coordenadas em uma tabela listando as coordenadas X e Y de cada ponto, seria necessário um esforço mental muito maior para calcular as distâncias entre os pontos, classifique a lista de distâncias e escolha a menor.

Como exemplo de uma consulta que não funciona bem visualmente, seria olhar para o céu noturno e, com base apenas na sua visão e em uma tabela de coordenadas de cada estrela, localizar a estrela mais próxima da Terra ou qual signo astrológico tem a menor distância entre elas. as estrelas em que consiste. Aqui você precisaria de um modelo 3D com zoom e girável para determinar isso visualmente, onde um computador consideraria que isso é essencialmente o mesmo problema que o original.

$O(1)$$O(1)$

A superioridade da inspeção visual depende de premissas cruciais que não podem ser garantidas em geral:

• $O(n)$

• count : (veja o comentário de Nick Alger sobre a resposta dada por DW) assuma uma contagem de pontos que exceda o número de suas células da retina - você nem sequer identificará todos os pontos envolvidos.

• variação : (cf. comentário de Nick Alger sobre a resposta dada por DW) pressupõe um conjunto de pontos em uma grade regular (por exemplo, hexagonal) sendo sujeita a pequenas perturbações aleatórias. se essas perturbações se tornarem menores que a resolução de sua retina (ou qualquer outra grade sobreposta), você não apenas será pressionado para detectar a distância mínima real, mas também escolherá os pares de pontos errados com alta probabilidade.

$O(n)$$O(1)$

1. O computador está resolvendo um problema diferente. É preciso uma lista de pontos, não uma imagem rasterizada de pontos. Converter de uma lista para uma imagem, ou seja, "plotar" os pontos, leva O(n)tempo.

   Rápido! Qual é o mais próximo (1,2):

   • (9, 9)
   • (5, 2)
   • (3, -2)
   • (4, 3)
   • (0, 4)
   • (1, 9)

   Muito mais difícil, certo? Aposto que se fizesse a lista duas vezes mais, você teria que fazer o dobro do trabalho.

2. Você não está ciente de quanto trabalho seu cérebro está fazendo. Você não "sabe" qual ponto está mais próximo. Seu cérebro está fazendo um trabalho computacional para descobrir essa resposta e disponibilizá-la. O cérebro trabalha em cada ponto em paralelo, portanto o tempo para terminar permanece aproximadamente o mesmo, mas a quantidade de trabalho necessário ainda aumenta com o número de pontos.

Pela mesma razão, quando você olha para um triângulo e sabe que é um triângulo, está esquecendo os muitos milhões de cálculos que faz sem perceber.

Redes neurais

Na verdade, você é uma rede neural treinada e carregada de massas e massas de dados.

Tome o jogo de classificação de formas infantis como exemplo:

Quando uma criança interage pela primeira vez com isso, é provável que ela tente inserir formas nos orifícios errados, porque ainda não treinou seu cérebro ou encontrou dados suficientes para construir redes. Eles não podem fazer suposições sobre arestas, tamanho, .etc para determinar qual forma se ajusta ao furo.

Isso parece óbvio para você (espero), porque você criou essas conexões, você pode até achar que é intuitivo e não precisa quebrá-las, por exemplo, você sabe que o triângulo se encaixa no triângulo e não precisa aproximar o tamanho , conte as arestas, .etc. Isso não é verdade, você fez tudo isso no seu subconsciente, o único pensamento consciente que você teve foi que é um triângulo. Muitos milhões de cálculos aconteceram ao se obter uma representação visual, entender o que estava representando, entender quais são os elementos individuais e, em seguida, estimar suas distâncias, o fato de você ter um grande banco de dados de informações para pesquisar tornou isso mais simples.

Seu cérebro não é binário

Os dados em que seu cérebro trabalha não são binários (tanto quanto sabemos), não são verdadeiros ou falsos, contém muitos estados que usamos para interpretar os dados, também cometeremos erros muitas vezes, mesmo quando seguimos as instruções corretas. processo, isso ocorre porque os dados mudam frequentemente. Eu arriscaria adivinhar que nossos cérebros funcionam muito mais como um computador quântico, onde os bits estão em um estado aproximado até serem lidos. Ou seja, se nosso cérebro funciona como um computador, ele realmente não é conhecido.

Portanto, um algoritmo para trabalhar com dados binários não funcionará da mesma maneira. Você não pode comparar os dois. Na sua cabeça, você está usando conceitos para executar tipos de dados avançados que contêm muito mais informações; você pode criar links onde eles não estão explicitamente definidos; ao ver um triângulo, você pode pensar no lado escuro da lua do Pink Floyd.

De volta ao gráfico de dispersão, não há razão para que você não possa fazer isso em um computador usando um bitmap e medindo a distância de um ponto em raios crescentes até encontrar outro ponto. É possivelmente o mais próximo que você pode chegar da aproximação de um humano. É provável que seja muito mais lento por causa da limitação de dados e porque nosso cérebro não se importa necessariamente com a complexidade da computação e toma uma rota complexa para fazer as coisas.

Não seria O (1), ou mesmo O (n) se n for o número de pontos, em vez disso, sua complexidade agora depende da distância linear máxima do ponto selecionado até o limite da imagem.

tl; dr

Seu cérebro não é um computador binário.

você está esquecendo um passo importante: plotando todos esses pontos no gráfico que está visualizando.

isso é necessariamente uma operação O (n).

depois disso, um computador pode usar o software de reconhecimento de imagem para encontrar os pontos aproximados mais próximos do centro da mesma maneira que o olho humano. Este é o pior cenário da operação O (sizeOfImage).

para que um humano faça o mesmo que o computador, lembre-se de que ele obtém uma lista de coordenadas e só pode olhar uma de cada vez.

Minha interpretação da pergunta:

Não acredito que essa questão deva ser tomada de maneira simplista como um problema de complexidade da geometria computacional. Deve ser melhor entendido como dizendo: percebemos a capacidade de encontrar a resposta em tempo constante, quando pudermos. O que explica essa percepção, e até essa explicação e as limitações humanas, também pode um computador.

$O(1)$$O(log( n))$

Isso pode ser reforçado pelas leis de Weber-Fechner , que afirmam que nossa percepção deve ser medida em uma escala logarítmica da medida física real. Em outras palavras, percebemos variações relativas em vez de variações absolutas. É por exemplo, por que a intensidade do som é medida em decibéis.

$O(log (n))$$O_\psi(log (log (n)))$$O_\psi$

$O_\psi(log (log (n)))$ que, para todos os efeitos práticos, provavelmente é perceptivelmente indistinguível de uma constante, e há necessariamente algum tempo constante adicionado a ela para iniciar o processo de reconhecimento e reconhecer o resultado.

Tendo em conta as limitações fisiológicas

A conclusão acima é sustentada ainda mais ao considerar as etapas de aquisição da imagem.

O OP teve o cuidado de separar a construção de uma estrutura de dados adequada ", como um quadtree", que é amortizada em várias consultas.

Isso não funciona para a maioria das pessoas que não memorizam a imagem. Acho que a imagem é digitalizada para cada consulta, mas isso não implica a digitalização de todos os pontos: não na primeira vez e não para consultas posteriores.

$T_{scan}$$T_{scan}$

$m$$O_\psi(log (log (m)))$

$2^{27}$$log_2(27)$

Sem conhecer as unidades reais a serem usadas, isso simplesmente mostra que a variação para processamento é, na pior das hipóteses, na mesma ordem que outras operações de tempo constante. Portanto, é bastante natural que o tempo percebido para encontrar o ponto mais próximo pareça constante. . . se determinamos o ponto mais próximo ou apenas um conjunto dos pontos mais próximos.

Sobre contra-exemplos e uma possível solução

É claro que é fácil criar contra-exemplos que dificultam muito a determinação dos olhos do ponto mais próximo entre uma pequena coleção de pontos mais próximos. É por isso que o OP está realmente pedindo um algoritmo que elimine rapidamente a maioria dos pontos, exceto os mais próximos. Essa questão da possível dificuldade de escolha entre vários pontos de fechamento é abordada em muitas respostas, com o exemplo paradigmático de pontos mais próximos estando quase em um círculo em torno do ponto de referência. Normalmente, as leis de Weber-Fechner impedem a capacidade de distinguir pequenas variações de distância em distâncias longas o suficiente. Esse efeito pode realmente ser aumentado pela presença de outros pontos que, embora eliminados, podem distorcer a percepção das distâncias. Portanto, tentar identificar o ponto mais próximo será uma tarefa mais difícil, e pode exigir etapas de exame específicas, como o uso de instrumentos, que destruirão completamente a sensação de tempo constante. Mas parece claramente fora da gama de experimentos considerados pelo OP, portanto, não é muito relevante.

A pergunta a ser respondida , que é a pergunta realmente feita pelo OP, é se existe uma maneira de eliminar a maioria dos pontos, exceto possivelmente os poucos restantes que parecem ter distâncias muito semelhantes ao ponto de referência.

$O(log(n))$

Rejeitar o custo amortizado não permite uma solução de computador, pois todos os pontos devem ser analisados. Isso ressalta uma grande diferença no poder computacional do cérebro e na percepção humana: ele pode usar a computação analógica com propriedades bastante diferentes da computação digital . Normalmente, esse é o caso quando bilhões de pontos não são distinguíveis a olho nu, que não têm a resolução de ver nada além de uma grande nuvem com vários tons de escuro. Mas o olho pode focalizar parte menor relevante e ver um número limitado de pontos, contendo os relevantes. Não precisa conhecer todos os pontos individualmente. Para um computador fazer o mesmo, seria necessário fornecer um sensor semelhante, em vez das coordenadas numéricas precisas de cada ponto. É um problema muito diferente.

A "mera inspeção visual" é, em alguns aspectos, muito mais poderosa que a computação digital. E isso se deve também à física dos sensores, não apenas a um poder computacional possivelmente maior do cérebro.

Tivemos estudantes em exames que, quando perguntados sobre a rapidez com que você pode classificar uma matriz, afirmam que os computadores são estúpidos e precisam de n * log (n) (ou pior), enquanto os humanos podem fazê-lo mais rapidamente.

A resposta do meu professor foi sempre: darei uma lista de 10.000 itens. Vamos ver se você consegue criar um método mais rápido do que o que um computador faria.

E então: quantos núcleos de processamento estão envolvidos quando você tenta encontrar o ponto mais próximo? Você não é uma máquina de processador único, possui uma rede neural que possui alguma flexibilidade quando se trata de tarefas como essa.

Acredito que @ Patrick87 deu a você a pista: seus olhos e cérebro são uma máquina de computação massivamente paralela. Alguns argumentaram que isso não explica o problema, porque, para problemas arbitrariamente grandes, um número finito de processadores paralelos não faz diferença.

Mas existe aqui: como sugerido por muitos, seus olhos (e cérebro) têm uma capacidade limitada de resolver esse problema; e isso ocorre porque não se pode encaixar nenhum número de pontos dentro do alcance de um olhar humano normal. Seus olhos precisam ser capazes de diferenciá-los para começar e, se houver muitos, estarão tão próximos que seus olhos não perceberão a diferença. Conclusão: é rápido para obter pontos suficientes que cabem na sua visão normal, ou seja, muito poucos. Noutros casos, irá falhar.

Portanto, você pode resolver esse problema em O (1) para casos pequenos e simples que seu cérebro pode processar rapidamente. Além disso, não pode e, portanto, não é nem O ( nada ), porque provavelmente falha.

Ninguém mencionou que esse problema pode ser resolvido muito rapidamente em um computador com um índice espacial. Isso equivale a plotar os pontos em uma imagem para que seus olhos digitalizem rapidamente e eliminem a maioria dos pontos.

Existe um algoritmo de indexação muito bom usado pelo Google e outros para encontrar o (s) ponto (s) mais próximo (s) chamado Geohash. http://en.wikipedia.org/wiki/Geohash .

Eu acho que isso vai equilibrar o concurso em favor do computador. Não fiquei impressionado com algumas das respostas que usavam o pensamento linear.

Se considerarmos o caso de encontrar vizinhos mais próximos em um conjunto de pontos de n-dimensões no espaço euclidiano, a complexidade é tipicamente limitada pelo número de dimensões à medida que cresce (por exemplo, maior que o tamanho do conjunto de dados).

$O(\log^{d-2} n)$

O problema de encontrar um ponto mais próximo de um nó em um gráfico tem uma expressão euclidiana sempre que o gráfico pode ser incorporado no espaço euclidiano com uma distorção pequena o suficiente. E usando uma lista de adjacências com pesos, ainda precisamos criar a lista de adjacências.

$O(1)$

outras respostas são boas, mas que tal uma pergunta contrária ao zen que estende o raciocínio / premissa básica da pergunta original a extremos para mostrar alguma falha [mas também é o paradoxo no centro da pesquisa em IA ]:

se consigo pensar com inteligência humana, por que não consigo criar um computador que pense tão bem quanto um humano?

existem várias maneiras de responder sua pergunta, mas, basicamente, nossos processos de pensamento e capacidades de percepção do cérebro não são necessariamente acessíveis à introspecção, e a introspecção que aplicamos a eles pode ser enganosa. por exemplo, podemos reconhecer objetos, mas não temos como perceber / explicar o processo quase algorítmico que continua permitindo isso. também existem muitos experimentos psicológicos que mostram que há distorções sutis em nossas percepções da realidade e, em particular, na percepção do tempo, veja, por exemplo, a percepção do tempo .

é geralmente considerado / conjecturado pelos cientistas que o cérebro humano de fato emprega algoritmos, mas eles funcionam de maneira diferente dos computadorizados, e também há uma quantidade muito grande de processamento paralelo acontecendo no cérebro através de redes neurais que não podem ser comparadas sensivelmente a algoritmos de computador seqüenciais . em mamíferos, uma porcentagem significativa de todo o volume cerebral é dedicada ao processamento visual.

em outras palavras, os cérebros humanos são, de muitas maneiras, computadores visuais altamente otimizados e, de fato, de várias maneiras, têm uma capacidade que excede os maiores supercomputadores do mundo atualmente, como reconhecimento de objetos, etc., e isso é devido a deficiências (em comparação) em software / hardware construído por humanos em comparação com a biologia que foi altamente ajustada / evoluída / otimizada ao longo de milhões de anos.

De um modo geral, você está resolvendo dois problemas diferentes e, se você competir na mesma competição, a complexidade será O (1) para os dois. Por quê? Vamos simplificar um pouco a situação - suponha que você tenha uma linha com um ponto vermelho e n pontos verdes. Sua tarefa é encontrar o ponto verde mais próximo do ponto vermelho. Tudo está no gráfico. Agora, o que você faz e o que programa está fazendo é basicamente o mesmo - basta "ir embora" (em ambas as direções) do ponto vermelho e verificar se o pixel que você está vendo é branco / preto (fundo) ou verde. Agora a complexidade é O (1).

O interessante é que alguns métodos de apresentação de dados respondem imediatamente a algumas perguntas (O (1)). O exemplo básico é extremamente simples - basta contar pixels brancos na imagem preta (cada valor de pixel é 0 = preto ou 1 = branco). O que você precisa fazer é adicionar todos os valores de pixels - a complexidade é a mesma para 1 pixel branco e para 1000, mas isso depende do tamanho da imagem - O (m), m = image.width * image.height. É possível fazer isso mais rápido? Obviamente, tudo o que precisamos fazer é usar um método diferente de armazenar imagens, que é uma imagem integral : Agora, o resultado do cálculo é O (1) (se você já tiver uma imagem integral calculada). Outra maneira é apenas armazenar todos os pixels brancos em array / vector / list / ... e apenas contar o tamanho - O (1).