Permettez-moi de préciser:

Étant donné le diagramme de dispersion d'un nombre donné de points n, si je veux trouver le point le plus proche d'un point du graphique, je peux immédiatement ignorer la plupart des points du graphique, réduisant ainsi mes choix à un petit nombre constant de points proches. .

Cependant, en programmation, étant donné un ensemble de points n, afin de trouver le point le plus proche de n’importe lequel, il faut vérifier tous les autres points, c’est-à-dire le temps .${\cal O}(n)$

Je devine que la vue visuelle d'un graphique équivaut probablement à une structure de données que je suis incapable de comprendre. car avec la programmation, en convertissant les points en une méthode plus structurée telle qu'un quadtree, on peut trouver les points les plus proches de points en n dans k ⋅ log ( n ) time ou ammortized O ( log n $k$$n$$k\cdot\log(n)$${\cal O}(\log n)$ temps.

Mais il n'y a toujours pas de O connu ( 1 )${\cal O}(1)$ algorithme amorti connu (que je puisse trouver) pour la recherche de points après la restructuration des données.

Alors, pourquoi cela semble-t-il possible avec une simple inspection visuelle?

Votre modèle de ce que vous faites mentalement est incorrect. En fait, vous opérez en deux étapes:

1. Éliminez tous les points qui sont trop loin, en temps .$O(1)$
2. Mesurer les points qui sont à peu près aussi près, à Θ ( m ) du temps.$m$$\Theta(m)$

Si vous avez joué à des jeux comme la pétanque ou le curling, cela devrait être familier - vous n'avez pas besoin d'examiner les objets qui sont très éloignés de la cible, mais vous devrez peut-être mesurer les concurrents les plus proches.

Pour illustrer ce point, quel point vert est le plus proche du point rouge? (Seulement par un peu plus de 1 pixel, mais il y en a un qui est le plus proche.) Pour faciliter les choses, les points ont même été codés en couleur par la distance.

Cette image contient points qui sont presque sur un cercle et n ≫ 10 points verts au total. Étape 1 vous permet d' éliminer tous , mais de m points, mais l' étape 2 nécessite de vérifier chacun des m points. Il n'y a pas de lien prioritaire pour m .$m=10$$n \gg 10$$m$$m$$m$

Une observation physique vous permet de réduire la taille du problème de l’ensemble des points à un ensemble restreint de m points. Cette étape n’est pas une étape de calcul au sens commun du terme, car elle repose sur un processus continu. Les processus continus ne sont pas soumis aux intuitions habituelles sur la complexité informatique, et en particulier à l'analyse asymptotique.$n$$m$

Maintenant, vous pouvez demander, pourquoi un processus continu ne peut-il pas résoudre complètement le problème? Comment arrive-t-il à ces points , pourquoi ne pouvons-nous pas affiner le processus pour obtenir m = 1 ?$m$$m=1$

$m$$n-m$

$(x,y)$$(\lfloor x \rfloor, \lfloor y \rfloor)$$(x_0, y_0)$$m$. Ce modèle respecte certaines propriétés clés du modèle humain:

• $m$
• L’efficacité pratique dépend de la sélection d’une échelle correspondant aux données (par exemple, vous n’économiserez rien si vos points sont sur du papier et que vos cellules mesurent 1 km de large).

La raison en est que les données ont été placées dans une "structure de données" optimisée pour cette requête et que le temps de prétraitement lors de la préparation du graphique doit être inclus dans vos temps mesurés, ce qui est proportionnel au nombre de points, ce qui donne un O (n). la complexité juste là.

Si vous placez les coordonnées dans un tableau répertoriant les coordonnées X et Y de chaque point, vous devrez déployer un effort mental beaucoup plus important pour calculer les distances entre les points, trier la liste des distances et choisir la plus petite.

Par exemple, une requête ne fonctionnant pas bien visuellement serait de regarder le ciel nocturne et - en vous basant uniquement sur votre vue et sur un tableau de coordonnées de chaque étoile - de localiser l'étoile la plus proche de la Terre ou le signe astrologique ayant le plus petit distance entre les étoiles il se compose. Ici, vous auriez besoin d’un modèle 3D zoomable et pivotable pour le déterminer visuellement, où un ordinateur considérerait qu’il s’agit essentiellement du même problème que votre original.

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

La supériorité de l'inspection visuelle repose sur des prémisses cruciales qui ne peuvent être garanties en général:

• $O(n)$

• count : (cf. commentaire de Nick Alger sur la réponse donnée par DW) supposons un nombre de points supérieur au nombre de vos cellules rétiniennes - vous ne pourrez même pas identifier tous les points impliqués.

• variance : (cf. commentaire de Nick Alger sur la réponse donnée par DW) supposons qu'un ensemble de points sur une grille régulière (par exemple hexagonale) soit soumis à de petites perturbations aléatoires. Si ces perturbations deviennent inférieures à la résolution de votre rétine (ou de toute autre grille superposée), non seulement vous aurez du mal à détecter la distance minimale réelle, mais vous sélectionnerez les mauvaises paires de points avec une probabilité élevée.

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

1. L'ordinateur résout un problème différent. Il faut une liste de points, pas une image pixellisée de points. La conversion d’une liste en une image, c’est-à-dire "tracer" les points, prend du O(n)temps.

   Rapide! Quel est le plus proche de (1,2):

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

   Beaucoup plus difficile, non? Je parie que si je faisais la liste deux fois plus longtemps, vous auriez à faire deux fois plus de travail.

2. Vous ne savez pas combien de travail votre cerveau fait. Vous ne "savez pas" simplement quel point est le plus proche. Votre cerveau effectue un travail informatique pour comprendre cette réponse et la rendre disponible. Le cerveau fonctionne sur chaque point en parallèle, de sorte que le temps de finition reste à peu près le même, mais la quantité de travail requise augmente toujours avec le nombre de points.

Pour la même raison, lorsque vous regardez un triangle et que vous savez que c’est un triangle, vous oubliez les millions de calculs que vous effectuez sans vous en rendre compte.

Les réseaux de neurones

En réalité, vous êtes un réseau de neurones formé et chargé de masses en masse de données.

Prenez par exemple le jeu de tri de formes pour bébés:

Lorsqu'un enfant interagit avec cela pour la première fois, il est probable qu'il tentera d'insérer des formes dans les mauvais trous, car il n'a pas encore formé son cerveau ni rencontré suffisamment de données pour créer des réseaux. Ils ne peuvent faire aucune supposition sur les arêtes, la taille, etc. pour déterminer quelle forme correspond au trou.

Cela vous semble évident (j'espère), car vous avez créé ces connexions. Vous pouvez même penser que c'est intuitif et que vous n'avez pas à la décomposer. Par exemple, vous savez que le triangle correspond au triangle et qu'il n'est pas nécessaire d'en approcher la taille. , compter les bords, .etc. Ce n'est pas vrai, vous avez fait tout cela dans votre subconscient, la seule pensée consciente que vous ayez eue est que c'est un triangle. Des millions de calculs ont été réalisés en prenant une représentation visuelle, en comprenant ce qu’elle représentait, en comprenant quels sont les éléments individuels, puis en estimant leurs distances, le fait que vous disposiez d’une vaste base de données d’informations à interroger a simplifié les choses.

Votre cerveau n'est pas binaire

Les données sur lesquelles votre cerveau fonctionne ne sont pas binaires (à notre connaissance), ni vraies ni fausses, elle contient de nombreux états que nous utilisons pour interpréter les données, nous nous trompons souvent, même lorsque nous suivons les bonnes processus, c’est que les données changent souvent. Je suppose que nos cerveaux fonctionnent beaucoup plus comme un ordinateur quantique où les bits sont approximativement en état de lecture. Autrement dit, si notre cerveau fonctionne comme un ordinateur, il n’est vraiment pas connu.

Par conséquent, un algorithme permettant de travailler avec des données binaires ne fonctionnera pas de la même manière. Vous ne pouvez pas comparer les deux. Dans votre tête, vous utilisez des concepts à exécuter, des types de données riches contenant beaucoup plus d'informations, vous avez la possibilité de créer des liens là où ils ne sont pas explicitement définis; en voyant un triangle, pensez au côté obscur de la couverture de lune de Pink Floyd.

Pour revenir au graphique en nuage de points, il n’ya aucune raison que vous ne puissiez pas le faire sur un ordinateur en utilisant une bitmap et en mesurant la distance d’un point à des rayons croissants jusqu’à ce que vous rencontriez un autre point. C'est peut-être le plus proche possible de l'approximation d'un humain. Il est probable que cela sera beaucoup plus lent en raison de la limitation des données et parce que notre cerveau ne se soucie pas nécessairement de la complexité du calcul et choisit une voie complexe pour faire les choses.

Ce ne serait pas O (1), ni même O (n) si n est le nombre de points, mais sa complexité dépend maintenant de la distance linéaire maximale entre le point sélectionné et une limite de l'image.

tl; dr

Votre cerveau n'est pas un ordinateur binaire.

vous oubliez une étape importante: tracer tous ces points sur le graphique que vous regardez.

c'est par nécessité une opération O (n).

après cela, un ordinateur peut utiliser un logiciel de reconnaissance d'image pour trouver les points approximatifs les plus proches du centre de la même manière que l'œil humain peut le faire. C'est le pire des cas pour l'opération O (sizeOfImage).

Pour qu'un humain fasse la même chose que l'ordinateur, rappelez-vous que l'ordinateur obtient une liste de coordonnées et qu'il ne peut en regarder qu'une à la fois.

Mon interprétation de la question:

Je ne crois pas que cette question doive être considérée de manière simpliste comme un problème de complexité géométrique algorithmique. Cela devrait être mieux compris comme disant: nous percevons une capacité à trouver la réponse en temps constant, quand nous le pouvons. Ce qui explique cette perception, et jusqu’à cette explication et aux limites humaines, peut aussi bien le faire un ordinateur.

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

Cela peut être renforcé par les lois de Weber-Fechner , qui stipulent que notre perception doit être mesurée sur une échelle logarithmique de la mesure physique réelle. En d'autres termes, nous percevons des variations relatives plutôt que des variations absolues. C'est par exemple pourquoi l'intensité sonore est mesurée en décibels.

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

$O_\psi(log (log (n)))$ ce qui, à toutes fins pratiques, est probablement indiscernablement perceptible d'une constante, et il faut nécessairement y ajouter un temps constant pour démarrer le processus de reconnaissance et reconnaître le résultat.

Prise en compte des limitations physiologiques

La conclusion ci-dessus est confirmée par les étapes d’acquisition d’images.

Le PO a pris soin de séparer la construction d’une structure de données appropriée, "telle qu’un arbre à quatre arbres", qui est amortie sur plusieurs requêtes.

Cela ne fonctionne pas pour la plupart des gens qui ne mémorisent pas l'image. Je pense que l'image est numérisée pour chaque requête, mais cela n'implique pas de numériser tous les points: pas la première fois, ni pour les requêtes ultérieures.

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

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

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

Sans connaître les unités réelles à utiliser, cela montre simplement que la variation pour le traitement est au pire dans le même ordre que les autres opérations à temps constant. Par conséquent, il est tout à fait naturel que le temps perçu pour trouver le point le plus proche soit constant. . . si nous déterminons le point le plus proche ou seulement un ensemble des points les plus proches.

A propos des contre-exemples et une solution possible

Il est bien sûr facile de construire des contre-exemples rendant très difficile la détermination visuelle du point le plus proche parmi une petite collection de points proches. C'est pourquoi l'OP demande en réalité un algorithme qui élimine rapidement la plupart des points, à l'exception des plus proches. Cette question de la difficulté possible de choisir entre plusieurs points proches est abordée dans de nombreuses réponses, l'exemple paradigmatique des points les plus proches se situant presque autour du point de référence. En règle générale, les lois de Weber-Fechner empêchent de pouvoir distinguer de petites variations de distance sur des distances suffisamment longues. Cet effet peut en réalité être augmenté par la présence d’autres points qui, bien que éliminés, risquent de fausser la perception des distances. Donc, essayer d'identifier le point le plus proche sera une tâche plus difficile, et peut nécessiter des étapes d’examen spécifiques, telles que l’utilisation d’instruments, qui détruiront complètement la sensation de temps constant. Mais cela semble clairement en dehors du champ des expériences envisagées par le PO, donc peu pertinent.

La question à laquelle répondre , qui est en réalité la question posée par le PO, est de savoir s'il est possible d'éliminer la plupart des points, à l'exception peut-être des derniers points qui semblent avoir des distances très proches du point de référence.

$O(log(n))$

Rejeter le coût amorti ne permet pas une solution informatique, car tous les points doivent être examinés. Cela souligne une différence majeure dans la puissance de calcul du cerveau et de la perception humaine: il peut utiliser le calcul analogique avec des propriétés assez différentes du calcul numérique . C'est typiquement le cas lorsque des milliards de points ne sont pas distinguables à l'œil nu, ce qui n'a pas la résolution de voir autre chose qu'un grand nuage avec différentes nuances de noir. Mais l'œil peut alors se concentrer sur une petite partie pertinente et voir un nombre limité de points contenant les pertinents. Il ne doit pas nécessairement connaître tous les points individuellement. Pour qu'un ordinateur fasse de même, vous devez lui attribuer un capteur similaire, plutôt que les coordonnées numériques précises de chaque point. C'est un problème très différent.

La "simple inspection visuelle" est à certains égards beaucoup plus puissante que le calcul numérique. Et cela est dû également à la physique des capteurs, et pas seulement à une puissance de calcul du cerveau probablement plus grande.

Lors des examens, nous avions des étudiants qui, lorsqu'on leur demandait à quelle vitesse vous pouvez trier un tableau, affirmaient que les ordinateurs sont stupides et ont besoin de n * log (n) (ou pire), alors que les humains peuvent le faire plus rapidement.

La réponse de mon professeur a toujours été: je donnerai une liste de 10 000 éléments. Voyons si vous pouvez trouver une méthode plus rapide que ne le ferait un ordinateur.

Et ensuite: combien de cœurs de traitement sont impliqués lorsque vous essayez de trouver le point le plus proche? Vous n'êtes pas une machine à processeur unique, vous avez un réseau de neurones, qui offre une certaine flexibilité pour des tâches comme celle-ci.

Je crois que @ Patrick87 vous a donné l’indice: vos yeux et votre cerveau sont une machine à calculer massivement parallèle. Certains ont fait valoir que cela n'expliquait pas le problème, car pour des problèmes arbitrairement grands, un nombre fini de processeurs parallèles ne fait aucune différence.

Mais c’est le cas ici: comme beaucoup l’ont laissé entendre, vos yeux (et votre cerveau) ont une capacité limitée à résoudre ce problème; et c’est parce qu’on ne peut tenir aucun nombre de points dans l’espace d’un regard humain normal. Vos yeux doivent être en mesure de les distinguer pour commencer, et s’ils sont trop nombreux, ils seront si proches que vos yeux ne remarqueront pas la différence. En bout de ligne: il est rapide pour assez de points qui correspondent à votre vision normale, c’est-à-dire très peu. Dans d'autres cas, cela échouera.

Ainsi, vous pouvez résoudre ce problème en O (1) pour les cas simples et de petite taille que votre cerveau peut traiter rapidement. Au-delà, cela ne peut pas et par conséquent, ce n'est même pas O ( n'importe quoi ) parce que cela échoue le plus probablement.

Personne n'a mentionné que ce problème peut être résolu très rapidement sur un ordinateur doté d'un index spatial. Cela équivaut à tracer les points d'une image pour permettre à vos yeux de numériser rapidement et d'éliminer la plupart des points.

Il existe un très bon algorithme d’indexation utilisé par Google et d’autres pour trouver le (s) point (s) le plus proche appelé Geohash. http://en.wikipedia.org/wiki/Geohash .

Je pense que cela va même augmenter le concours en faveur de l'ordinateur. Je n'ai pas été impressionné par certaines des réponses utilisant la pensée linéaire.

Si nous considérons le cas de la recherche de voisins les plus proches dans un ensemble de points de n dimensions dans un espace euclidien, la complexité est généralement limitée par le nombre de dimensions à mesure qu’il grossit (c’est-à-dire plus grand que la taille de l’ensemble de données).

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

Le problème de la recherche du point le plus proche d’un nœud dans un graphe a une expression euclidienne chaque fois que le graphe peut être incorporé dans l’espace euclidien avec une distorsion suffisamment petite. Et en utilisant une liste de contiguïté avec des poids, nous avons encore besoin de construire la liste de contiguïté.

$O(1)$

les autres réponses sont bonnes, mais qu’en est-il d’une question posée par zen qui étire à l’extrême le raisonnement de base de la question initiale pour montrer un défaut [mais constitue également le paradoxe au cœur de la recherche sur l’IA ]:

si je peux penser avec une intelligence humaine, pourquoi ne puis-je pas créer un ordinateur qui pense aussi bien qu'un humain?

Il existe plusieurs façons de répondre à votre question, mais au fond, nos processus de pensée et nos capacités de perception cérébrale ne sont pas nécessairement accessibles à l'introspection, et l'introspection que nous leur appliquons peut être trompeuse. par exemple, nous pouvons reconnaître des objets mais nous n'avons aucun moyen de percevoir / expliquer le processus quasi-algorithmique qui le permet. de nombreuses expériences de psychologie montrent également que nos perceptions de la réalité et de notre perception du temps présentent de subtiles distorsions, comme par exemple la perception du temps .

Les scientifiques pensent généralement que le cerveau humain utilise des algorithmes, mais qu'ils fonctionnent différemment des ordinateurs, et qu'il existe également une très grande quantité de traitements parallèles dans le cerveau via des réseaux de neurones qui ne peuvent être comparés de manière judicieuse. algorithmes informatiques séquentiels . chez les mammifères, un pourcentage important du volume total du cerveau est dédié au traitement visuel.

en d'autres termes, les cerveaux humains sont à bien des égards des ordinateurs visuels hautement optimisés, et ils ont en fait à bien des égards une capacité qui dépasse les plus grands supercalculateurs du monde actuellement, comme la reconnaissance d'objets, etc., en raison de lacunes (en comparaison). dans les logiciels / matériels construits par l'homme par rapport à la biologie qui a été hautement optimisée / évoluée / optimisée sur des millions d'années.

En règle générale, vous résolvez deux problèmes différents et si vous concourez dans la même compétition, la complexité sera de 0 (1) pour vous deux. Pourquoi? Simplifions un peu la situation - supposons que vous ayez une ligne avec un point rouge et n points verts. Votre tâche consiste à trouver le point vert le plus proche du point rouge. Tout est sur le graphique. Maintenant, ce que vous faites et ce que vous programmez est fondamentalement le même - il suffit de "s'éloigner" (dans les deux sens) du point rouge et de vérifier si le pixel que vous regardez est blanc / noir (arrière-plan) ou vert. Maintenant, la complexité est O (1).

Ce qui est intéressant, c’est que certaines méthodes de présentation des données permettent de répondre immédiatement à certaines questions (O (1)). L'exemple de base est extrêmement simple: il suffit de compter les pixels blancs sur une image noire (chaque pixel vaut 0 = noir ou 1 = blanc). Ce que vous devez faire, c'est simplement ajouter toutes les valeurs en pixels - la complexité est la même pour 1 pixel blanc et 1 000, mais cela dépend de la taille de l'image - O (m), m = image.width * image.height. Est-il possible de le faire plus rapidement? Bien sûr, tout ce que nous avons à faire est d’utiliser différentes méthodes de stockage des images : l’ image intégrale : le résultat obtenu est donc O (1) (si vous avez déjà une image intégrale calculée). Une autre méthode consiste simplement à stocker tous les pixels blancs dans un tableau / vecteur / liste / ... et à simplement compter sa taille - O (1).