Warum kann ich eine Grafik betrachten und sofort den nächstgelegenen Punkt zu einem anderen Punkt finden, aber ich benötige O (n) Zeit für die Programmierung?

122

Lassen Sie mich erklären:

Wenn ich bei einem Streudiagramm mit einer bestimmten Anzahl von Punkten n mental den nächsten Punkt zu einem beliebigen Punkt im Diagramm finden möchte, kann ich die meisten Punkte im Diagramm sofort ignorieren und meine Auswahl auf eine kleine, konstante Anzahl von Punkten in der Nähe eingrenzen .

Bei der Programmierung muss jedoch, wenn eine Menge von Punkten n gegeben ist, um den nächstgelegenen Punkt zu einem beliebigen Punkt zu finden, jeder zweite Punkt überprüft werden, nämlich die -Zeit.O(n)

Ich vermute, dass das visuelle Sehen eines Graphen wahrscheinlich einer Datenstruktur entspricht, die ich nicht verstehen kann. Denn beim Programmieren kann man durch Konvertieren der Punkte in eine strukturiertere Methode wie einen Quadtree die nächsten Punkte zu Punkten in in finden oder amortisiert zeit.knO ( log n )kLog(n)O(Logn)

Es sind jedoch noch keine amortisierten Algorithmen (die ich finden kann) für die Punktsuche nach einer Datenumstrukturierung bekannt.O(1)

Warum scheint dies bei bloßer Sichtprüfung möglich zu sein?

Ari
quelle
36
Sie kennen alle Punkte bereits und ungefähr, wo sie sich befinden. Die "Softwaretreiber" für Ihre Augen haben bereits die harte Arbeit für Sie geleistet, das Bild zu interpretieren. In Ihrer Analogie halten Sie diese Arbeit für "kostenlos", obwohl dies in Wirklichkeit nicht der Fall ist. Wenn Sie bereits eine Datenstruktur hätten, die die Punktpositionen in eine Art Oktobaumdarstellung aufteilt, könnten Sie viel bessere Ergebnisse erzielen als mit O (n). Eine Menge Vorverarbeitung findet im Unterbewusstsein Ihres Gehirns statt, bevor die Informationen auch nur den bewussten Teil erreichen. Vergiss das nie in solchen Analogien.
Richard Tingle
20
Ich denke, dass zumindest eine Ihrer Annahmen im Allgemeinen nicht zutrifft. Es sei angenommen, dass alle Punkte auf einem Kreis mit 'kleinen' Störungen angeordnet sind und 1 zusätzlicher Punkt P der Mittelpunkt des Kreises ist. Wenn Sie den nächstgelegenen Punkt zu P finden möchten, können Sie keinen der anderen Punkte im Diagramm schließen.
Collapsar
4
Weil unser Gehirn wirklich erstaunlich ist! Klingt nach einer billigen Antwort, ist aber wahr. Wir wissen wirklich nicht viel darüber, wie unsere (scheinbar massiv parallele) Bildverarbeitung funktioniert.
Carl Witthoft
7
Im Grunde genommen nutzt Ihr Gehirn die Raumaufteilung, ohne dass Sie es merken. Die Tatsache, dass dies sehr schnell aussieht, bedeutet nicht, dass es eine konstante Zeit ist - Sie arbeiten mit einer endlichen Auflösung, und Ihre Bildverarbeitungssoftware ist darauf ausgelegt (und könnte dies sogar parallel verarbeiten). Die Tatsache, dass Sie hundert Millionen kleine CPUs für die Vorverarbeitung verwenden, versetzt Sie nicht in - es führt nur die komplizierte Operation auf vielen kleinen Prozessoren aus. Und vergessen Sie nicht, auf das 2D-Papier zu zeichnen - das allein muss mindestens . O ( n )O(1)O(n)
Luaan
9
Ich bin mir nicht sicher, ob es bereits erwähnt wurde, aber das menschliche Gehirn arbeitet ganz anders als ein Computersystem vom Typ SISD von Neumann. Von besonderer Bedeutung ist dabei, dass das menschliche Gehirn meines Wissens von Natur aus parallel ist, insbesondere wenn es darum geht, sensorische Reize zu verarbeiten: Man kann mehrere Dinge gleichzeitig hören, sehen und fühlen und ist sich (in etwa) dessen bewusst von allen gleichzeitig. Ich konzentriere mich darauf, einen Kommentar zu schreiben, sehe aber meinen Schreibtisch, eine Dose Soda, meine Jacke an der Tür, den Stift auf meinem Schreibtisch usw. Ihr Gehirn kann viele Punkte gleichzeitig überprüfen.
Patrick87

Antworten:

115

Dein Modell dessen, was du mental tust, ist falsch. In der Tat arbeiten Sie in zwei Schritten:

  1. Beseitigen Sie alle zu weit entfernten Punkte in .O(1)
  2. Messen Sie die Punkte, die ungefähr so ​​nah sind, in Zeit.Θ ( m )mΘ(m)

Wenn Sie Pétanque (Boccia) oder Curling gespielt haben, sollte dies bekannt sein - Sie müssen nicht die Objekte untersuchen, die sehr weit vom Ziel entfernt sind, aber Sie müssen möglicherweise die nächsten Konkurrenten messen.

Um diesen Punkt zu veranschaulichen, welcher grüne Punkt ist dem roten Punkt am nächsten? (Nur um etwas mehr als 1 Pixel, aber es gibt einen, der am nächsten ist.) Um die Sache einfacher zu machen, wurden die Punkte sogar nach Entfernung farblich gekennzeichnet.

eine Wolke von Punkten

Dieses Bild enthält Punkte, die fast auf einem Kreis liegen, und insgesamt grüne Punkte. In Schritt 1 können Sie alle bis auf etwa Punkte entfernen, in Schritt 2 müssen Sie jedoch jeden der Punkte überprüfen . Es gibt keine a priori-Grenze für .n » 10 m m mm=10n10mmm

Bei einer physischen Beobachtung können Sie die Problemgröße von der gesamten Menge von Punkten auf eine eingeschränkte Kandidatenmenge von Punkten verkleinern . Dieser Schritt ist kein allgemein bekannter Berechnungsschritt, da er auf einem kontinuierlichen Prozess basiert. Kontinuierliche Prozesse unterliegen nicht den üblichen Intuitionen über die Komplexität der Berechnungen und insbesondere der asymptotischen Analyse.mnm

Nun fragen Sie sich vielleicht, warum ein kontinuierlicher Prozess das Problem nicht vollständig lösen kann. Wie kommt es zu diesen Punkten ? Warum können wir den Prozess nicht verfeinern, um ?m = 1mm=1

Die Antwort ist, dass ich ein bisschen geschummelt habe: Ich präsentierte eine Menge von Punkten, die erzeugt werden, um aus fast nächsten Punkten und Punkten zu bestehen, die weiter entfernt sind. Im Allgemeinen erfordert die Bestimmung, welche Punkte innerhalb einer genauen Grenze liegen, eine genaue Beobachtung, die Punkt für Punkt durchgeführt werden muss. Bei einem groben Eliminierungsprozess können Sie viele offensichtliche Nichtkandidaten ausschließen. Um jedoch zu entscheiden, welche Kandidaten noch übrig sind, müssen sie aufgelistet werden.n - mmnm

Sie können dieses System in einer diskreten Computerwelt modellieren. Angenommen, die Punkte werden in einer Datenstruktur dargestellt, die sie in Zellen auf einem Gitter sortiert, dh der Punkt wird in einer Liste für die Zelle gespeichert . Wenn Sie nach den Punkten suchen, die am nächsten liegen, und die Zelle, die diesen Punkt enthält, höchstens einen weiteren Punkt enthält, ist es ausreichend, die enthaltende Zelle und die 8 benachbarten Zellen zu überprüfen. Die Gesamtpunktzahl in diesen 9 Zellen beträgt . Dieses Modell berücksichtigt einige Schlüsseleigenschaften des menschlichen Modells:( x , y ) ( x 0 , y 0 ) m(x,y)(x,y)(x0,y0)m

  • m ist potentiell unbegrenzt - ein entartet schlechterer Fall von zB Punkten, die fast auf einem Kreis liegen, ist immer möglich.
  • Die praktische Effizienz hängt davon ab, ob Sie eine Skala ausgewählt haben, die den Daten entspricht (z. B. sparen Sie nichts, wenn sich Ihre Punkte auf einem Stück Papier befinden und Ihre Zellen 1 km breit sind).
Gilles
quelle
9
Darüber hinaus können nicht alle Diagramme in die Ebene projiziert werden, sodass die Euklidischen Abstände mit den Abständen im Diagramm übereinstimmen (z. B. wenn die Kantengewichte keine Metrik bilden).
Raphael
5
@Raphael Ich habe die Frage so verstanden, dass es eher um Computergeometrie als um Graphentheorie geht, aber dies ist in der Tat eine zusätzliche Komplikation.
Gilles
2
@ Gilles Done . Ich habe gerade den Begriff Computergeometrie gelernt .
Gerrit
2
Dies mag ein Trottel sein, ich kann verstehen, was Sie zu zeigen versuchen, aber wenn jemand farbenblind ist, "wählen Sie das Grün, das dem Rot am nächsten liegt", kratzt er viel am Kopf darüber, welche Punkte welche sind. Denken Sie auch in Zukunft darüber nach - wählen Sie andere Farbkombinationen als Rot / Grün!
tpg2114
3
@ tpg2114 Vergiss nicht, dass Rot / Grün nicht die einzige Art von Farbenblindheit ist. Das Zeigen mit Form (oder einem anderen Attribut als Farbe) wäre noch umfassender als "alle anderen Farbkombinationen außer Rot / Grün".
Jonathan Van Matre
42

Der Grund dafür ist, dass die Daten in einer für diese Abfrage optimierten "Datenstruktur" abgelegt wurden und dass die Vorverarbeitungszeit bei der Erstellung des Diagramms in die gemessenen Zeiten einbezogen werden sollte, die proportional zur Anzahl der Punkte ist und ein O (n) ergibt. Komplexität genau dort.

Wenn Sie die Koordinaten in eine Tabelle aufnehmen, in der die X- und Y-Koordinaten der einzelnen Punkte aufgeführt sind, wäre ein viel größerer mentaler Aufwand erforderlich, um die Entfernungen zwischen den Punkten zu berechnen, die Liste der Entfernungen zu sortieren und die kleinste zu wählen.

Als Beispiel für eine Abfrage, die visuell nicht gut funktioniert, können Sie den Nachthimmel betrachten und - basierend auf Ihrer Ansicht und einer Koordinatentabelle für jeden Stern - den erdnächsten Stern oder das Sternzeichen mit dem geringsten Abstand ermitteln die sterne, aus denen es besteht. Hier würden Sie ein zoombares und drehbares 3D-Modell benötigen, um dies visuell zu bestimmen, wobei ein Computer dies als im Wesentlichen dasselbe Problem wie Ihr Original ansehen würde.

Thorbjørn Ravn Andersen
quelle
2
+1 - Ich habe nach unten geblättert und nach jemandem gesucht, der genau diesen Punkt macht. Die Darstellung eingehender Daten ist wichtig - versuchen Sie einfach, den Median einer sortierten Liste gegenüber einer unsortierten zu ermitteln!
Cloudfeet
21

Diese Frage geht von einer fehlerhaften Prämisse aus. Sie denken nur, Sie können mental den nächsten Punkt in Punkt finden, aber in der Tat, wenn Sie nicht können. Es fühlt sich so an, weil Sie es gewohnt sind, mit sehr kleinen Diagrammen umzugehen, aber kleine Beispiele können irreführend sein, wenn es um asymptotische Komplexität geht. Wenn Sie dies mit einem Streudiagramm mit einer Milliarde Punkten versuchen, werden Sie schnell feststellen, dass Sie dies nicht in O ( 1 ) Zeit tun können .O(1)O(1)

DW
quelle
8
Stellen Sie sich vor, Sie platzieren eine Milliarde Punkte entlang eines Kreises, aber alle sind ein wenig verstört, sodass Ihre Punkte einen verschwommenen Ring bilden. Um den Punkt zu finden, der dem Zentrum am nächsten liegt, sehe ich nicht, wie Sie es viel besser machen können, als alle Punkte einzeln zu überprüfen.
Nick Alger
4
@NickAlger Es ist also eher so O(numberOfPointsAboutTheSameDistanceFromTheTargetPointAsTheClosestPoint), was nicht unbedingt damit zu tun hat n. In jedem Fall denke ich, dass eine Antwort darauf mögliche Datenstrukturen in Bezug darauf darstellen sollte, wie der menschliche Verstand sie wahrnimmt und abfragt. Einfach zu sagen, dass es nicht O (1) ist, fühlt sich ... faul an? unzureichend?
Dukeling
5
@Dukeling O (etwas) bezieht sich auf den schlimmsten Fall. Wenn es Layouts gibt, in denen das menschliche Gehirn es nicht in konstanter Zeit schafft, dann ist es definitiv nicht O (1). Wenn es ein Limit X gibt, bei dem das menschliche Gehirn X Punkte in konstanter Zeit verarbeiten kann, aber X * 2 Punkte überhaupt nicht verarbeiten kann - dann ist es nicht O (1).
Peteris
3
@Dukeling Es ist notwendigerweise abhängig von n, da es im schlimmsten Fall gleich n ist, und wenn Sie n willkürliche Punkte angegeben haben, müssen Sie damit rechnen, dass es unmöglich sein kann, es schneller als C * n-Operationen auszuführen.
Peteris
2
@Peteris Ich denke, wir sind uns nicht einig darüber, was es bedeutet, "unbedingt abhängig von n" zu sein und wie man die nächstgelegene Obergrenze bestimmt.
Dukeling
15

Die Überlegenheit der Sichtprüfung hängt von entscheidenden Voraussetzungen ab, die im Allgemeinen nicht garantiert werden können:

  • O(n)

  • count : (vgl. Kommentar von Nick Alger zur Antwort von DW) Gehen Sie von einer Punktzahl aus, die die Anzahl Ihrer Netzhautzellen übersteigt - Sie werden nicht einmal alle beteiligten Punkte identifizieren.

  • Varianz : (vgl. Kommentar von Nick Alger zur Antwort von DW) Nehmen Sie an, dass eine Menge von Punkten auf einem regulären (z. B. hexagonalen) Gitter kleinen zufälligen Störungen ausgesetzt ist. Wenn diese Störungen die Auflösung Ihrer Netzhaut (oder eines anderen überlagerten Gitters) unterschreiten, müssen Sie nicht nur den tatsächlichen Mindestabstand ermitteln, sondern mit hoher Wahrscheinlichkeit die falschen Punktpaare auswählen.

O(n)O(1)

Collapsar
quelle
1
O(n)O(lOG(n))
O(n)nO(nLogn)n
15
  1. Der Computer löst ein anderes Problem. Es wird eine Liste von Punkten erstellt, kein gerastertes Bild von Punkten. Das Umwandeln von einer Liste in ein Bild, dh das "Zeichnen" der Punkte, dauert einige O(n)Zeit.

    Schnell! Welches ist am nächsten an (1,2):

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

    Viel schwerer, oder? Ich wette, wenn ich die Liste doppelt so lang machen würde, müssten Sie doppelt so viel Arbeit machen.

  2. Sie sind sich nicht bewusst, wie viel Arbeit Ihr Gehirn leistet. Sie wissen nicht "nur", welcher Punkt näher ist. Ihr Gehirn arbeitet am Rechnen, um diese Antwort herauszufinden und verfügbar zu machen. Das Gehirn arbeitet an jedem Punkt parallel, sodass die Zeit bis zum Abschluss ungefähr gleich bleibt, der Arbeitsaufwand jedoch mit der Anzahl der Punkte zunimmt.

Craig Gidney
quelle
13

Aus dem gleichen Grund vergessen Sie, wenn Sie ein Dreieck betrachten und wissen, dass es ein Dreieck ist, die vielen Millionen Berechnungen, die Sie ausführen, ohne es zu bemerken.

Neuronale Netze

Tatsächlich sind Sie ein neuronales Netzwerk, das mit Massen von Daten trainiert und geladen wurde.

Nehmen Sie das Sortierspiel für Säuglingsformen als Beispiel:

Bildbeschreibung hier eingeben

Wenn ein Kind zum ersten Mal damit interagiert, ist es wahrscheinlich, dass es versucht, Formen in die falschen Löcher einzufügen. Dies liegt daran, dass es sein Gehirn noch nicht trainiert hat oder nicht genügend Daten gefunden hat, um Netzwerke aufzubauen. Sie können keine Annahmen über Kanten, Größe usw. treffen, um zu bestimmen, welche Form zum Loch passt.

Dies scheint Ihnen offensichtlich zu sein (ich hoffe), da Sie diese Verbindungen hergestellt haben und vielleicht sogar denken, dass sie intuitiv sind und nicht abgebaut werden müssen. Beispielsweise wissen Sie nur, dass das Dreieck zum Dreieck passt und dass Sie die Größe nicht approximieren müssen , zähle die Kanten, etc. Dies ist nicht wahr, Sie haben alles in Ihrem Unterbewusstsein getan, der einzige bewusste Gedanke, den Sie hatten, war, dass es ein Dreieck ist. Viele Millionen von Berechnungen erfolgten, indem eine visuelle Repräsentation erstellt, ihre Repräsentation verstanden, die einzelnen Elemente erkannt und ihre Abstände geschätzt wurden. Die Tatsache, dass Sie über eine große Datenbank mit Informationen verfügten, gegen die abgefragt werden musste, machte dies einfacher.

Dein Gehirn ist nicht binär

Die Daten, an denen Ihr Gehirn arbeitet, sind nicht binär (so weit wir wissen), nicht wahr oder falsch. Sie enthalten viele Zustände, die wir zur Interpretation der Daten verwenden. Wir machen auch häufig Fehler, selbst wenn wir den richtigen folgen Dies liegt daran, dass sich die Daten häufig ändern. Ich würde eine Vermutung wagen, dass unser Gehirn viel mehr wie ein Quantencomputer funktioniert, bei dem sich die Bits bis zum Lesen in einem ungefähren Zustand befinden. Das heißt, wenn unser Gehirn überhaupt wie ein Computer funktioniert, ist es wirklich nicht bekannt.

Daher funktioniert ein Algorithmus zum Arbeiten mit Binärdaten nicht gleich. Sie können die beiden nicht vergleichen. In Ihrem Kopf verwenden Sie Konzepte für die Ausführung umfangreicher Datentypen, die weitaus mehr Informationen enthalten. Sie haben die Möglichkeit, Verknüpfungen dort zu erstellen, wo sie nicht explizit definiert sind. Wenn Sie ein Dreieck sehen, können Sie an Pink Floyds dunkle Seite der Monddecke denken.

Bildbeschreibung hier eingeben

Zurück zum Streudiagramm gibt es keinen Grund, warum Sie dies auf einem Computer nicht mit einer Bitmap und dem Messen des Abstands von einem Punkt in zunehmenden Radien durchführen können, bis Sie auf einen anderen Punkt stoßen. Es ist wahrscheinlich das Beste, was Sie einer menschlichen Annäherung erreichen können. Aufgrund der Datenbeschränkung und weil sich unser Gehirn nicht unbedingt um die Komplexität der Berechnungen kümmert und einen komplexen Weg einschlägt, um Dinge zu erledigen, ist dies wahrscheinlich viel langsamer.

Es wäre nicht O (1) oder sogar O (n), wenn n die Anzahl der Punkte ist. Stattdessen hängt seine Komplexität jetzt von der maximalen linearen Entfernung zwischen dem ausgewählten Punkt und einem Bildrand ab.

tl; dr

Ihr Gehirn ist kein Binärcomputer.


George Reith
quelle
8

Sie vergessen einen wichtigen Schritt: Zeichnen Sie alle diese Punkte auf dem Diagramm, das Sie betrachten.

Dies ist notwendigerweise eine O (n) -Operation.

Danach kann ein Computer die Bilderkennungssoftware verwenden, um die ungefähren Punkte zu finden, die dem Zentrum am nächsten liegen, ähnlich wie es das menschliche Auge kann. Dies ist der schlimmste Fall einer O-Operation (sizeOfImage).

Wenn ein Mensch dasselbe wie der Computer tun soll, muss beachtet werden, dass der Computer eine Liste mit Koordinaten erhält und immer nur eine anzeigen kann.

Ratschenfreak
quelle
1
Wenn man eine konstante "Auflösung" wählt, kann man einen Algorithmus verwenden, der die Zeit O (log (Auflösung)) pro Punkt ist, um sie zu zeichnen und alle Punkte zu identifizieren, die "nahe" am interessierenden Punkt liegen. Das O (log (Auflösung)) entspricht in etwa der Tatsache, dass es länger dauert, Punkte genau auf Papier zu zeichnen, als dies weniger genau zu tun. Es ist auch zu beachten, dass eine Erhöhung der Auflösung die Kosten für alle Punkte von Algorithmen erhöht, um nicht in Frage kommende Punkte zu eliminieren, aber die Anzahl der nicht nächstgelegenen Punkte verringert, die die Eliminierung überleben.
Supercat
7

Meine Interpretation der Frage:

Ich glaube nicht, dass diese Frage vereinfacht als Problem der rechnerischen Geometriekomplexität aufzufassen ist. Es sollte besser verstanden werden als: Wir nehmen die Fähigkeit wahr, die Antwort in konstanter Zeit zu finden, wenn wir können. Was diese Wahrnehmung und bis zu dieser Erklärung und bis zu menschlichen Einschränkungen erklärt, kann auch ein Computer.

O(1)O(lOG(n))

Dies kann durch die Weber-Fechner-Gesetze untermauert werden , die besagen, dass unsere Wahrnehmung auf einer logarithmischen Skala des tatsächlichen physikalischen Maßes gemessen werden soll. Mit anderen Worten, wir nehmen eher relative als absolute Schwankungen wahr. Dies ist zum Beispiel der Grund, warum die Schallintensität in Dezibel gemessen wird.

O(lOG(n))Oψ(lOG(lOG(n)))Oψ

Oψ(lOG(lOG(n))) Dies ist für alle praktischen Zwecke wahrscheinlich wahrnehmungsmäßig nicht von einer Konstanten zu unterscheiden, und es wird notwendigerweise eine konstante Zeit hinzugefügt, um den Erkennungsprozess zu starten und das Ergebnis zu bestätigen.

Berücksichtigung der physiologischen Grenzen

Die obige Schlussfolgerung wird weiter gestützt, wenn die Bildaufnahmeschritte betrachtet werden.

Das OP achtete darauf, den Aufbau einer ordnungsgemäßen Datenstruktur, "wie eines Quadtrees", zu trennen, der bei mehreren Abfragen abgeschrieben wird.

Dies funktioniert bei den meisten Menschen nicht, die sich das Bild nicht merken. Ich denke, das Bild wird für jede Abfrage gescannt, aber das bedeutet nicht, dass alle Punkte gescannt werden: nicht beim ersten Mal und nicht für spätere Abfragen.

TsceinnTsceinn

mOψ(lOG(lOG(m)))

227lOG2(27)

Ohne die tatsächlich zu verwendenden Einheiten zu kennen, zeigt dies einfach, dass die Variation für die Verarbeitung im schlimmsten Fall in derselben Größenordnung liegt wie andere Operationen mit konstanter Zeit. Daher ist es ganz natürlich, dass sich die wahrgenommene Zeit zum Finden des nächstgelegenen Punkts konstant anfühlt. . . ob wir den nächsten Punkt oder nur eine Menge der näheren Punkte bestimmen.

Über Gegenbeispiele und eine mögliche Lösung

Es ist natürlich leicht, Gegenbeispiele zu erstellen, die die Bestimmung des nächstgelegenen Punktes aus einer kleinen Sammlung von näheren Punkten für die Augen sehr schwierig machen. Aus diesem Grund fordert das OP tatsächlich einen Algorithmus, mit dem die meisten Punkte, mit Ausnahme der nächstgelegenen, schnell beseitigt werden. Dieses Problem der möglichen Schwierigkeit, zwischen mehreren Nahpunkten zu wählen, wird in vielen Antworten angesprochen, wobei sich das paradigmatische Beispiel der nächsten Punkte fast auf einem Kreis um den Referenzpunkt befindet. Typischerweise steht das Weber-Fechner-Gesetz der Unterscheidung kleiner Entfernungsschwankungen über ausreichend lange Entfernungen entgegen. Dieser Effekt kann tatsächlich durch das Vorhandensein anderer Punkte verstärkt werden, die, obwohl beseitigt, die Wahrnehmung von Entfernungen verfälschen können. Es wird also schwieriger sein, den nächstgelegenen Punkt zu identifizieren. und kann durchaus spezielle Untersuchungsschritte erfordern, wie die Verwendung von Instrumenten, die das Gefühl konstanter Zeit vollständig zerstören. Es scheint jedoch eindeutig außerhalb des vom OP berücksichtigten Bereichs von Experimenten zu liegen, weshalb es nicht sehr relevant ist.

Die zu beantwortende Frage , die vom OP tatsächlich gestellt wird, lautet, ob es eine Möglichkeit gibt, die meisten Punkte zu beseitigen, mit Ausnahme möglicherweise der wenigen verbleibenden Punkte, die sehr ähnliche Abstände zum Referenzpunkt zu haben scheinen.

O(lOG(n))

Die Ablehnung von fortgeführten Anschaffungskosten ermöglicht keine Computerlösung, da alle Punkte geprüft werden müssen. Dies unterstreicht einen großen Unterschied in der Rechenleistung des Gehirns und der menschlichen Wahrnehmung: Es kann analoge Berechnungen mit Eigenschaften verwenden, die sich von digitalen Berechnungen deutlich unterscheiden . Dies ist in der Regel der Fall, wenn Milliarden von Punkten mit dem Auge nicht zu erkennen sind, da es nicht die Auflösung hat, etwas anderes als eine große Wolke mit verschiedenen Dunkeltönen zu sehen. Das Auge kann sich dann jedoch auf einen relevanten kleineren Teil konzentrieren und eine begrenzte Anzahl von Punkten sehen, die die relevanten Punkte enthalten. Es müssen nicht alle Punkte einzeln bekannt sein. Damit ein Computer dasselbe tut, müsste er einen ähnlichen Sensor haben und nicht die genauen numerischen Koordinaten jedes Punkts. Das ist ein ganz anderes Problem.

"Bloße Sichtprüfung" ist in mancher Hinsicht viel leistungsfähiger als digitale Berechnung. Und das liegt auch an der Physik der Sensoren, nicht nur an einer möglicherweise höheren Rechenleistung des Gehirns.

babou
quelle
O(1)O(Logn) O(1)O(1)O(Logn)wenn Sie eine Aufgabe lösen, die sich der Wahrnehmung entzieht, z. B. eine bestimmte Zahl in einer grafischen Darstellung eines ausgeglichenen binären Heaps mit beschrifteten Knoten suchen. Beachten Sie, dass Wahrnehmungsbeschränkungen keine Rolle spielen, da Sie die Grafiken nur lokal überprüfen.
Collapsar
n
Oψ(lOG(lOG(n)))
4

Wir hatten Studenten in Prüfungen, die, wenn sie gefragt wurden, wie schnell Sie ein Array sortieren können, behaupten, dass Computer dumm sind und n * log (n) (oder noch schlimmer) benötigen, während Menschen dies schneller können.

Die Antwort meines Professors war immer: Ich werde eine Liste von 10.000 Artikeln geben. Mal sehen, ob Sie eine Methode finden können, die schneller ist als ein Computer.

Und dann: Wie viele Prozessorkerne sind beteiligt, wenn Sie versuchen, den nächstgelegenen Punkt zu finden? Sie sind keine Einzelprozessor-Maschine, Sie haben ein neuronales Netzwerk, das bei solchen Aufgaben eine gewisse Flexibilität besitzt.

Zane
quelle
1
Plus die verschiedenen Aspekte dessen, was Sie über die Daten wissen und welche Ressourcen Ihnen zum Sortieren zur Verfügung stehen. Zum Beispiel, wenn Ihre Kommilitonen etwas sortieren müssen, das nicht vollständig in den Raum passt, den sie sind.
Thorbjørn Ravn Andersen
@ ThorbjørnRavnAndersen: Dies ist ein schönes Beispiel, um zu verstehen, wie wichtig Raumkomplexität ist "etwas, das nicht vollständig in den Raum passt" 8 ^)
Zane
3

Ich glaube, @ Patrick87 hat Ihnen den Hinweis gegeben: Ihre Augen und Ihr Gehirn sind eine sehr parallele Rechenmaschine. Einige argumentierten, dass dies das Problem nicht erklärt, da für beliebig große Probleme eine begrenzte Anzahl von Parallelprozessoren keinen Unterschied macht.

Aber hier ist es so: Wie von vielen angedeutet, haben Ihre Augen (und Ihr Gehirn) eine begrenzte Fähigkeit, dieses Problem zu lösen. und das liegt daran, dass man keine beliebige Anzahl von Punkten in die Spannweite eines normalen menschlichen Blicks einpassen kann. Ihre Augen müssen sie zunächst unterscheiden können, und wenn es zu viele gibt, sind sie so nah, dass Ihre Augen den Unterschied nicht bemerken. Fazit: Es ist schnell genug, um Punkte zu erzielen, die in Ihre normale Sicht passen, dh nur sehr wenige. In anderen Fällen wird es fehlschlagen.

So können Sie dieses Problem in O (1) für kleine und einfache Fälle lösen, die Ihr Gehirn im Handumdrehen verarbeiten kann. Darüber hinaus kann es nicht und deshalb ist es nicht einmal O ( irgendetwas ), weil es höchstwahrscheinlich versagt.

Carlosayam
quelle
1

Niemand hat erwähnt, dass dieses Problem auf einem Computer mit einem räumlichen Index sehr schnell gelöst werden kann. Dies entspricht dem Zeichnen der Punkte in einem Bild, damit Ihre Augen schnell scannen und die meisten Punkte entfernen können.

Es gibt einen sehr guten Indexierungsalgorithmus, der von Google und anderen verwendet wird, um die nächsten Punkte zu finden, die als Geohash bezeichnet werden. http://en.wikipedia.org/wiki/Geohash .

Ich denke, dass dies sogar den Wettbewerb zugunsten des Computers verschärfen wird. Einige der Antworten, bei denen lineares Denken zum Einsatz kam, haben mich nicht beeindruckt.

user3451435
quelle
Θ(n) Θ(lgn)
Der Punkt ist, dass ein räumlicher Index es ungefähr so ​​einfach macht wie es für einen Menschen ist, der auf einen mit Punkten übersäten Bildschirm schaut.
Reinierpost
1

Wenn wir den Fall betrachten, in einem Punktsatz von n-Dimensionen im euklidischen Raum einen nächsten Nachbarn zu finden, ist die Komplexität in der Regel durch die Anzahl der Dimensionen begrenzt, wenn sie größer werden (dh größer als der Datensatz).

O(Logd-2n)

Das Problem, einen Punkt in der Nähe eines Knotens in einem Diagramm zu finden, hat einen euklidischen Ausdruck, wenn das Diagramm mit einer ausreichend kleinen Verzerrung in den euklidischen Raum eingebettet werden kann. Und wenn wir eine Adjazenzliste mit Gewichten verwenden, müssen wir die Adjazenzliste noch erstellen.

O(1)

user13675
quelle
-1

Andere Antworten sind gut, aber wie wäre es mit einer Zen-Gegenfrage, die die grundlegende Argumentation / Prämisse der ursprünglichen Frage auf das Äußerste ausdehnt, um einige Fehler zu zeigen [aber auch das Paradoxon im Kern der KI-Forschung ]:

Wenn ich mit menschlicher Intelligenz denken kann, warum kann ich dann keinen Computer schaffen, der genauso gut denkt wie ein Mensch?

Es gibt mehrere Möglichkeiten, Ihre Frage zu beantworten, aber im Grunde genommen sind unsere Denkprozesse und Gehirnwahrnehmungsfähigkeiten nicht unbedingt für die Selbstbeobachtung zugänglich, und die Selbstbeobachtung, die wir auf sie anwenden, kann irreführend sein. Zum Beispiel können wir Objekte erkennen, aber wir haben keine Möglichkeit, den quasi-algorithmischen Prozess, der dies ermöglicht, wahrzunehmen / zu erklären. Es gibt auch viele psychologische Experimente, die zeigen, dass es subtile Verzerrungen in unserer Wahrnehmung der Realität und insbesondere der Zeitwahrnehmung gibt, siehe z . B. Zeitwahrnehmung .

Im Allgemeinen wird von Wissenschaftlern vermutet, dass das menschliche Gehirn tatsächlich Algorithmen einsetzt , diese jedoch anders funktionieren als computergestützte, und es findet im Gehirn eine sehr große Menge an Parallelverarbeitung über neuronale Netze statt , die nicht sinnvoll zu vergleichen ist sequentielle Computeralgorithmen. Bei Säugetieren entfällt ein erheblicher Prozentsatz des gesamten Gehirnvolumens auf die visuelle Verarbeitung.

Mit anderen Worten, menschliche Gehirne sind in vielerlei Hinsicht hochoptimierte visuelle Computer, und sie verfügen tatsächlich in vielerlei Hinsicht über eine Fähigkeit, die die derzeit weltweit größten Supercomputer übertrifft, wie z. in menschlich konstruierter Software / Hardware im Vergleich zu Biologie, die über Millionen von Jahren hochgradig abgestimmt / weiterentwickelt / optimiert wurde.

vzn
quelle
O(f(n))
-2

Im Allgemeinen lösen Sie zwei verschiedene Probleme, und wenn Sie im selben Wettbewerb antreten, wird die Komplexität für Sie beide 0 (1). Warum? Machen wir die Situation etwas einfacher - nehmen wir an, Sie haben eine Linie mit einem roten Punkt und n grünen Punkten. Ihre Aufgabe ist es, einen grünen Punkt zu finden, der dem roten Punkt am nächsten kommt. Alles ist in der Grafik. Was Sie jetzt tun und was Sie programmieren, ist im Grunde dasselbe - gehen Sie einfach (in beide Richtungen) vom roten Punkt weg und überprüfen Sie, ob das Pixel, auf das Sie schauen, weiß / schwarz (Hintergrund) oder grün ist. Jetzt ist die Komplexität O (1).

Interessant ist, dass einige Datenpräsentationsmethoden sofort Antworten auf einige Fragen geben (O (1)). Das grundlegende Beispiel ist sehr einfach: Zählen Sie nur weiße Pixel auf einem schwarzen Bild (jeder Pixelwert ist 0 = schwarz oder 1 = weiß). Sie müssen lediglich alle Pixelwerte hinzufügen - die Komplexität ist für 1 weißes Pixel und für 1000 Pixel gleich, hängt jedoch von der Bildgröße ab - O (m), m = image.width * image.height. Ist es möglich, es schneller zu machen? Natürlich müssen wir nur eine andere Methode zum Speichern von Bildern verwenden, nämlich das Integralbild : Die Bildbeschreibung hier eingeben Berechnung des Ergebnisses lautet nun O (1) (wenn Sie das Integralbild bereits berechnet haben). Eine andere Möglichkeit besteht darin, alle weißen Pixel in Array / Vektor / Liste / ... zu speichern und die Größe zu zählen - O (1).

Cyriel
quelle
O(1)O(1)
@FrankW - wie komplex ist es, wegzugehen? Ich versuche nicht zu sagen, dass Sie sich irren, ich möchte es nur wissen. Zählen der Größe des Arrays / Vektors / der Liste - im Allgemeinen ist die Arraygröße konstant, sodass es nicht erforderlich ist, den Vektor zu zählen - ich bin mir nicht sicher, ich würde sagen, dass dies von der Implementierung abhängt (aber in den meisten Implementierungen ist dies wahrscheinlich nur ein Bereich von ein Objekt, so dass es nicht nötig ist, es zu zählen), liste auf - du hast recht, es ist nicht O (1) - mein Fehler.
Cyriel
kkO(#pichXels)