Por que posso olhar para um gráfico e encontrar imediatamente o ponto mais próximo de outro ponto, mas levo tempo O (n) através da programação?

122

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 .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 )knklog(n)O(logn)

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

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

Ari
fonte
36
Você já está ciente de todos os pontos e aproximadamente onde eles estão; os "drivers de software" para seus olhos já fizeram o trabalho duro de interpretar a imagem. Na sua analogia, você está considerando este trabalho "gratuito" quando, na realidade, não é. Se você já tinha uma estrutura de dados que dividia as posições dos pontos em algum tipo de representação de octotree, poderia fazer muito melhor que O (n). Muito pré-processamento acontece na parte subconsciente do seu cérebro antes que a informação chegue à parte consciente; nunca esqueça isso nesse tipo de analogia.
Richard Tingle
20
Acho que pelo menos uma de suas suposições não se aplica em geral. assuma todos os pontos dispostos em um círculo com perturbações 'pequenas' e 1 ponto adicional P sendo o centro do círculo. Se você deseja encontrar o ponto mais próximo de P, não pode descartar nenhum dos outros pontos no gráfico.
colapsar
4
Porque nosso cérebro é realmente incrível! Parece uma resposta barata, mas é verdade. Realmente não sabemos muito sobre como o nosso processamento de imagens (aparentemente paralelo em massa) funciona.
Carl Witthoft
7
Bem, basicamente, seu cérebro usa particionamento de espaço sem você perceber. O fato de isso parecer muito rápido não significa que seja um tempo constante - você está trabalhando com uma resolução finita e seu software de processamento de imagem foi projetado para isso (e pode até estar lidando com tudo isso paralelamente). O fato de você estar usando centenas de milhões de pequenas CPUs para fazer o pré-processamento não o coloca em - apenas faz a operação complicada em muitos pequenos processadores. E não esqueça a plotagem para o artigo 2D - que por si deve ser pelo menos . O ( n )O(1)O(n)
Luaan 17/03/14
9
Não tenho certeza se já foi mencionado, mas o cérebro humano funciona de maneira muito diferente de um sistema de computação do tipo SISD von Neumann. Particularmente relevante aqui é que, como eu o entendo, o cérebro humano é inerentemente paralelo e especialmente quando se trata de processar estímulos sensoriais: você pode ouvir, ver e sentir várias coisas ao mesmo tempo e estar (grosso modo, de qualquer maneira) consciente de todos eles simultaneamente. Estou concentrado em escrever um comentário, mas vejo minha mesa, uma lata de refrigerante, minha jaqueta pendurada na porta, a caneta na minha mesa, etc. Seu cérebro pode verificar muitos pontos simultaneamente.
Patrick87

Respostas:

115

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Θ(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.

uma nuvem de pontos

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 mm=10n10mmm

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.mnm

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 = 1mm=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 - mmnm

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 ) m(x,y)(x,y)(x0,y0)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).
Gilles
fonte
9
Além disso, nem todos os gráficos podem ser projetados na planície para que as distâncias euclidianas correspondam às distâncias no gráfico (por exemplo, se os pesos das arestas não formarem uma métrica).
Raphael
5
@ Rafael Entendi a pergunta como sendo sobre geometria computacional, e não sobre teoria dos grafos, mas na verdade essa é uma complicação adicional.
Gilles
2
@Gilles Done . Acabei de aprender o termo geometria computacional .
gerrit
2
Pode ser uma escolha difícil, eu posso entender o que você está tentando mostrar, mas como alguém que é daltônico "escolhe o verde mais próximo do vermelho" leva a muita cabeça coçando sobre quais pontos são quais. Apenas algo para se pensar no futuro - escolha qualquer outra combinação de cores além de vermelho / verde!
tpg2114
3
@ tpg2114 Não se esqueça de vermelho / verde não é o único tipo de daltonismo. Mostrá-lo com forma (ou qualquer atributo que não seja cor) seria ainda mais inclusivo do que "qualquer outra combinação de cores além de vermelho / verde".
Jonathan Van Matre
42

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.

Thorbjørn Ravn Andersen
fonte
2
+1 - eu estava rolando para baixo procurando alguém que fizesse exatamente esse ponto. A representação dos dados recebidos é importante - basta tentar encontrar a mediana de uma lista classificada versus uma não classificada!
cloudfeet
21

O(1)O(1)

DW
fonte
8
Imagine colocar um bilhão de pontos ao longo de um círculo, mas todos um pouco perturbados, para que seus pontos formem um anel de aparência confusa. Para encontrar o ponto mais próximo do centro a olho nu, não vejo como você poderia fazer muito melhor do que verificar todos os pontos um por um.
Nick Alger
4
@NickAlger Então é mais parecido O(numberOfPointsAboutTheSameDistanceFromTheTargetPointAsTheClosestPoint), o que não está necessariamente relacionado n. De qualquer maneira, acho que uma resposta a isso deve apresentar possíveis estruturas de dados em termos de como a mente humana as percebe e as consulta. Simplesmente dizer que não é O (1) parece preguiçoso? inadequado?
Dukeling 17/03/14
5
@Dukeling O (alguma coisa) refere-se ao pior caso. Se existem layouts em que o cérebro humano não pode fazê-lo em tempo constante, então definitivamente não é O (1). Se existe algum limite X em que o cérebro humano pode processar X pontos em tempo constante, mas não pode processar X * 2 pontos - então não é O (1).
31413 Peteris
3
@ Dukeling Depende necessariamente de n, já que, na pior das hipóteses, é igual a n, e se você forneceu n pontos arbitrários, deve esperar que seja impossível fazê-lo mais rapidamente do que as operações C * n.
31413 Peteris
2
@ Peteris Acho que discordamos sobre o que significa ser "necessariamente dependente de n" e como determinar o limite superior mais próximo.
Dukeling 17/03/14
15

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)

colapsar
fonte
1
O(n)O(log(n))
O(n)nO(nlogn)n
15
  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.

Craig Gidney
fonte
13

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:

insira a descrição da imagem aqui

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.

insira a descrição da imagem aqui

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.


George Reith
fonte
8

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.

catraca arrepiante
fonte
1
Se alguém escolhe uma "resolução" constante, pode-se usar um algoritmo que é o tempo O (log (resolução)) por ponto para plotá-los e identificar todos os pontos que estão "próximos" ao ponto de interesse. O O (log (resolução)) é vagamente análogo ao fato de levar mais tempo para plotar pontos com precisão no papel do que fazê-lo com menos precisão. Observe também que o aumento da resolução aumentará o custo de todos os pontos dos algoritmos para eliminar pontos não candidatos, mas reduzirá o número de pontos não mais próximos que sobreviverão à eliminação.
Supercat
7

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ψ(log(log(n)))Oψ

Oψ(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.

TscanTscan

mOψ(log(log(m)))

227log2(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.

babou
fonte
O(1)O(logn) O(1)O(1)O(logn)quando você resolve uma tarefa além do reconhecimento perceptivo absoluto, por exemplo, localizar um determinado número em uma representação gráfica de um heap binário equilibrado com nós rotulados. observe que as restrições perceptivas não importam, pois você só inspeciona os gráficos localmente.
colapsar
n
Oψ(log(log(n)))
4

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.

Zane
fonte
1
Além disso, os vários aspectos do que você sabe sobre os dados e quais recursos você tem disponível quando precisa classificar. Por exemplo, se seus colegas precisam classificar algo que não se encaixa completamente na sala em que estão.
Thorbjørn Ravn Andersen
@ ThorbjørnRavnAndersen: este é um agradável para entender o quão importante espaço-complexidade é "algo que não pode caber completamente na sala" 8 ^)
Zane
3

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.

carlosayam
fonte
1

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.

user3451435
fonte
Θ(n) Θ(lgn)
A questão é que um índice espacial o torna tão fácil quanto é para um humano olhando para uma tela cheia de pontos.
Reinierpost 24/03
1

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(logd2n)

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)

user13675
fonte
-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.

vzn
fonte
O(f(n))
-2

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 : insira a descrição da imagem aqui 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).

cyriel
fonte
O(1)O(1)
@ FrankW - então, qual é a complexidade de "ir embora"? Não estou tentando dizer que você está errado, só quero saber. Contar o tamanho da matriz / vetor / lista - geralmente o tamanho da matriz é constante, portanto não há necessidade de contar, vetor - não tenho certeza, diria que depende da implementação (mas provavelmente na maioria das implementações é apenas um campo de um objeto para que não seja necessário contá-lo), liste - você está certo, não é O (1) - meu erro.
Cyriel 22/03
kkO(#pixels)