Dlaczego mogę spojrzeć na wykres i od razu znaleźć najbliższy punkt do innego punktu, ale programowanie zajmuje mi O (n) czasu?

122

Pozwól mi wyjaśnić:

Biorąc pod uwagę wykres punktowy pewnej liczby punktów n, jeśli chcę znaleźć mentalnie najbliższy punkt do dowolnego punktu na wykresie, mogę natychmiast zignorować większość punktów na wykresie, zawężając moje wybory do niewielkiej, stałej liczby punktów w pobliżu .

Jednak przy programowaniu, biorąc pod uwagę zestaw punktów n, aby znaleźć punkt najbliższy dowolnemu, wymaga sprawdzenia każdego innego punktu, którym jest czas.O(n)

Zgaduję, że wizualny widok wykresu prawdopodobnie odpowiada pewnej strukturze danych, której nie jestem w stanie zrozumieć; ponieważ przy programowaniu, poprzez konwersję punktów na bardziej ustrukturyzowaną metodę, taką jak quadtree, można znaleźć najbliższe punkty do punktów za w czasie lub zamrożone czas.knklog(n)O(logn)

Ale wciąż nie są znane zamortyzowane algorytmy (które mogę znaleźć) do wyszukiwania punktów po restrukturyzacji danych.O(1)

Dlaczego więc wydaje się to możliwe po zwykłej kontroli wizualnej?

Ari
źródło
36
Jesteś świadomy wszystkich punktów już z grubsza, gdzie one są; „sterowniki oprogramowania” dla twoich oczu wykonały już ciężką pracę nad interpretacją obrazu. W swojej analogii uważasz tę pracę za „bezpłatną”, podczas gdy w rzeczywistości tak nie jest. Jeśli masz już strukturę danych, która podzieliła pozycje punktowe na jakąś reprezentację oktotree, możesz zrobić znacznie lepiej niż O (n). Wiele procesów wstępnego przetwarzania zachodzi w podświadomej części mózgu, zanim informacja dotrze nawet do części świadomej; nigdy nie zapominaj o tym w tego rodzaju analogiach.
Richard Tingle,
20
Myślę, że co najmniej jedno z twoich założeń nie odnosi się ogólnie. załóżmy, że wszystkie punkty ułożone są na okręgu z „małymi” zaburzeniami, a 1 dodatkowy punkt P jest środkiem koła. Jeśli chcesz znaleźć punkt najbliższy P, nie możesz odrzucić żadnego z pozostałych punktów na wykresie.
Collapsar
4
Ponieważ nasz mózg jest naprawdę niesamowity! Brzmi jak tania odpowiedź, ale to prawda. Naprawdę nie wiemy zbyt wiele o tym, jak działa nasze (pozornie masowo równoległe) przetwarzanie obrazu.
Carl Witthoft
7
Zasadniczo twój mózg używa podziału przestrzeni bez zauważenia. Fakt, że pojawia się to naprawdę szybko, nie oznacza, że ​​jest to ciągły czas - pracujesz z pewną skończoną rozdzielczością, a oprogramowanie do przetwarzania obrazu jest do tego przeznaczone (a może nawet radzi sobie z tym wszystkim równolegle). Fakt, że używasz stu milionów małych procesorów do wstępnego przetwarzania, nie stawia cię w - po prostu wykonuje skomplikowaną operację na wielu małych procesorach. I nie zapomnij o kreśleniu na papierze 2D - który sam musi być co najmniej O ( n ) . O(1)O(n)
Luaan,
9
Nie jestem pewien, czy zostało już wspomniane, ale ludzki mózg działa zupełnie inaczej niż system obliczeniowy typu SISD von Neumann. Szczególnie istotne jest to, że, jak rozumiem, ludzki mózg jest z natury równoległy, a szczególnie, jeśli chodzi o przetwarzanie bodźców zmysłowych: możesz słyszeć, widzieć i odczuwać wiele rzeczy w tym samym czasie i być (z grubsza, w każdym razie) świadomym wszystkich jednocześnie. Koncentruję się na pisaniu komentarza, ale widzę biurko, puszkę napoju gazowanego, kurtkę wiszącą na drzwiach, długopis na biurku itp. Twój mózg może sprawdzić wiele punktów jednocześnie.
Patrick87

Odpowiedzi:

115

Twój model tego, co robisz mentalnie, jest nieprawidłowy. W rzeczywistości działasz w dwóch etapach:

  1. Wyeliminuj wszystkie punkty, które są za daleko, w czasie .O(1)
  2. Zmierz punktów, które są mniej więcej tak blisko, w czasie Θ ( m ) .mΘ(m)

Jeśli grałeś w gry takie jak bule (bule) lub curling, powinno to być znane - nie musisz badać obiektów, które znajdują się bardzo daleko od celu, ale możesz potrzebować zmierzyć najbliższych rywali.

Aby zilustrować ten punkt, która zielona kropka jest najbliższa czerwonej kropce? (Tylko o nieco ponad 1 piksel, ale jest jeden, który jest najbliższy.) Aby ułatwić, kropki zostały nawet oznaczone kolorami według odległości.

chmura punktów

To zdjęcie zawiera punktów, które są prawie na okręgu, i n łącznie 10 zielonych punktów. Krok 1 pozwala wyeliminować wszystkie z wyjątkiem m punktów, ale krok 2 wymaga sprawdzenia każdego z m punktów. Nie ma a priori związanego dla m .m=10n10mmm

Obserwacja fizyczna pozwala zmniejszyć rozmiar problemu z całego zestawu punktów do ograniczonego zestawu kandydackiego m punktów. Ten krok nie jest krokiem obliczeniowym, jak powszechnie rozumiane, ponieważ opiera się na ciągłym procesie. Procesy ciągłe nie podlegają zwykłym intuicjom dotyczącym złożoności obliczeniowej, a w szczególności analizie asymptotycznej.nm

Teraz możesz zapytać, dlaczego ciągły proces nie może całkowicie rozwiązać problemu? Jak dochodzi do tych punktów, dlaczego nie możemy dopracować procesu, aby uzyskać m = 1 ?mm=1

Odpowiedź brzmi: oszukałem trochę: przedstawiłem zestaw punktów, który jest generowany, aby składał się z prawie najbliższych punktów i n - m punktów, które są dalej. Zasadniczo ustalenie, które punkty mieszczą się w precyzyjnej granicy, wymaga precyzyjnej obserwacji, którą należy wykonać punkt po punkcie. Zgrubny proces eliminacji pozwala wykluczyć wielu oczywistych kandydatów niebędących kandydatami, ale samo podjęcie decyzji, którzy pozostali kandydaci, wymaga ich wyliczenia.mn-m

Możesz modelować ten system w dyskretnym świecie obliczeniowym. Załóżmy, że punkty są reprezentowane w strukturze danych, która sortuje je do komórek na siatce, tzn. Punkt jest przechowywany na liście dla komórki ( x , y ) . Jeśli szukasz punktów najbliższych ( x 0 , y 0 ), a komórka zawierająca ten punkt zawiera co najwyżej jeden inny punkt, wystarczy sprawdzić komórkę zawierającą i 8 sąsiednich komórek. Całkowita liczba punktów w tych 9 komórkach wynosi m(x,r)(x,r)(x0,r0)m. Ten model uwzględnia niektóre kluczowe właściwości modelu ludzkiego:

  • jest potencjalnie nieograniczony - zdegenerowany gorszy przypadek np. punktów leżących prawie na okręgu jest zawsze możliwy.m
  • Praktyczna wydajność zależy od wybrania skali odpowiadającej danym (np. Nic nie zaoszczędzisz, jeśli twoje kropki są na kawałku papieru, a komórki mają 1 km szerokości).
Gilles
źródło
9
Co więcej, nie wszystkie wykresy mogą być rzutowane na płaszczyznę, tak aby odległości Euklidesa pasowały do ​​odległości na wykresie (np. Jeśli ciężary krawędzi nie tworzą metryki).
Raphael
5
@Raphael Zrozumiałem pytanie jako o geometrii obliczeniowej, a nie teorii grafów, ale w rzeczywistości jest to dodatkowa komplikacja.
Gilles
2
@Gilles Done . Właśnie nauczyłem się pojęcia geometria obliczeniowa .
gerrit
2
Może to być drobiazg, rozumiem, co próbujesz pokazać, ale ponieważ ten, kto jest ślepy na kolory, „wybiera najbliższą zieleń od czerwonej”, prowadzi do rozmyślań, które punkty są które. Pomyśl o tym w przyszłości - wybierz inne kombinacje kolorów oprócz czerwonego / zielonego!
tpg2114
3
@ tpg2114 Nie zapominaj, że czerwony / zielony nie jest jedynym rodzajem ślepoty na kolory. Pokazanie go z kształtem (lub dowolnym atrybutem innym niż kolor) byłoby jeszcze bardziej uwzględniające niż „jakiekolwiek inne kombinacje kolorów oprócz czerwonego / zielonego”.
Jonathan Van Matre
42

Powodem jest to, że dane zostały umieszczone w „strukturze danych” zoptymalizowanej dla tego zapytania i że czas przygotowania do przygotowania wykresu powinien zostać uwzględniony w zmierzonych czasach, który jest proporcjonalny do liczby kropek, dając O (n) złożoność właśnie tam.

Jeśli umieścisz współrzędne w tabeli zawierającej współrzędne X i Y każdego punktu, będziesz potrzebował znacznie większego wysiłku umysłowego, aby obliczyć odległości między punktami, posortuj listę odległości i wybierz najmniejszą.

Jako przykład zapytania, które nie działa dobrze wizualnie, mogłoby być spojrzenie na nocne niebo i - na podstawie wyłącznie twojego widoku i tabeli współrzędnych każdej gwiazdy - zlokalizowanie najbliższej gwiazdy na Ziemi lub który znak astrologiczny ma najmniejszą odległość między gwiazdy, z których się składa. Potrzebny byłby tutaj model 3D z możliwością powiększania i obracania, aby określić go wizualnie, przy czym komputer uznałby to za zasadniczo ten sam problem, co oryginał.

Thorbjørn Ravn Andersen
źródło
2
+1 - Przewijałem w dół, szukając kogoś, kto właśnie to robi. Reprezentacja przychodzących danych jest ważna - po prostu spróbuj znaleźć medianę posortowanej listy w porównaniu z nieposortowaną!
cloudfeet
21

To pytanie zaczyna się od błędnego założenia. Po prostu myślisz, że możesz mentalnie znaleźć najbliższy punkt w punkcie , ale w rzeczywistości, jeśli nie możesz. Wydaje się, że tak jest, ponieważ przywykłeś do radzenia sobie z bardzo małymi grafami, ale małe przykłady mogą wprowadzać w błąd, gdy mamy do czynienia z asymptotyczną złożonością. Jeśli spróbujesz to zrobić za pomocą wykresu punktowego z miliardem punktów, szybko odkryjesz, że nie możesz tego zrobić w czasie O ( 1 ) .O(1)O(1)

DW
źródło
8
Wyobraź sobie, że umieszczasz miliard punktów wzdłuż koła, ale wszystkie lekko się trochę zaburzyły, więc twoje punkty tworzą niewyraźnie wyglądający pierścień. Aby znaleźć punkt znajdujący się najbliżej środka oka, nie widzę, jak można by to zrobić znacznie lepiej niż sprawdzanie wszystkich punktów jeden po drugim.
Nick Alger
4
@NickAlger Więc to bardziej jak O(numberOfPointsAboutTheSameDistanceFromTheTargetPointAsTheClosestPoint), co niekoniecznie jest związane z n. Tak czy inaczej, uważam, że odpowiedź na to pytanie powinna przedstawiać możliwe struktury danych pod względem tego, jak ludzki umysł je postrzega i pyta. Mówiąc wprost, że to nie O (1) wydaje się ... leniwy? niewystarczający?
Dukeling,
5
@Dukeling O (coś) odnosi się do najgorszego przypadku. Jeśli istnieją układy, w których ludzki mózg nie może tego zrobić w stałym czasie, to zdecydowanie nie jest to O (1). Jeśli istnieje jakiś limit X, w którym ludzki mózg może przetwarzać punkty X w stałym czasie, ale w ogóle nie może przetwarzać X * 2 punktów - to nie jest to O (1).
Peteris,
3
@Dukeling Koniecznie jest zależny od n, ponieważ w najgorszym przypadku jest równy n, a jeśli podałeś n dowolnych punktów, musisz spodziewać się, że może być niemożliwe, aby zrobić to szybciej niż operacje C * n.
Peteris,
2
@Peteris Chyba nie zgadzamy się, co to znaczy być „koniecznie zależnym od n” i jak ustalić najbliższą górną granicę.
Dukeling,
15

Przewaga kontroli wzrokowej zależy od kluczowych pomieszczeń, których ogólnie nie można zagwarantować:

  • skalowanie : skupiasz się na graficznej reprezentacji obszaru zainteresowania. oznacza to, że geometria została zmniejszona, aby pasowała do twojego pola widzenia. w ustawieniach ogólnych wymaga to już czasu na wstępne przetwarzanie.O(n)

  • count : (por. komentarz Nicka Algera do odpowiedzi udzielonej przez DW) zakłada liczbę punktów przekraczającą liczbę komórek siatkówki - nawet nie zidentyfikujesz wszystkich zaangażowanych punktów.

  • wariancja : (por. komentarz Nicka Algera do odpowiedzi udzielonej przez DW) zakłada, że ​​zbiór punktów na regularnej (np. heksagonalnej) siatce jest poddawany niewielkim przypadkowym zaburzeniom. jeśli te zaburzenia staną się niższe niż rozdzielczość twojej siatkówki (lub jakiejkolwiek innej nałożonej siatki), będziesz nie tylko trudny do wykrycia rzeczywistej minimalnej odległości, ale wybierzesz niewłaściwe pary punktów z dużym prawdopodobieństwem.

O(n)O(1)

Collapsar
źródło
1
O(n)O(losol(n))
O(n)nO(nlogn)n
15
  1. Komputer rozwiązuje inny problem. Wymaga listy punktów, a nie zrasteryzowanego obrazu punktów. Konwersja listy na obraz, tj. „Wykreślanie” punktów, zajmuje dużo O(n)czasu.

    Szybki! Który jest najbliższy (1,2):

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

    O wiele trudniej, prawda? Założę się, że jeśli zrobię listę dwa razy dłużej, będziesz musiał wykonać dwa razy więcej pracy.

  2. Nie zdajesz sobie sprawy, ile pracy wykonuje twój mózg. Nie „po prostu wiesz”, który punkt jest bliżej. Twój mózg wykonuje prace obliczeniowe, aby znaleźć tę odpowiedź i ją udostępnić. Mózg pracuje nad każdym punktem równolegle, więc czas na ukończenie pozostaje mniej więcej taki sam, ale ilość wymaganej pracy wciąż rośnie wraz z liczbą punktów.

Craig Gidney
źródło
13

Z tego samego powodu, kiedy patrzysz na trójkąt i wiesz, że jest to trójkąt, zapominasz o milionach obliczeń, które wykonujesz, nie zauważając go.

Sieci neuronowe

W efekcie jesteś siecią neuronową, która została przeszkolona i obciążona masą mas masowych danych.

Weźmy za przykład grę sortowania kształtów niemowląt:

wprowadź opis zdjęcia tutaj

Gdy dziecko po raz pierwszy wejdzie w interakcję z tym, prawdopodobnie spróbuje wstawić kształty do niewłaściwych otworów, ponieważ nie wyszkoliło jeszcze swojego mózgu lub nie napotkało wystarczającej ilości danych do zbudowania sieci. Nie mogą przyjmować założeń dotyczących krawędzi, rozmiaru itp., Aby określić, który kształt pasuje do otworu.

Wydaje ci się to oczywiste (mam nadzieję), ponieważ zbudowałeś te połączenia, możesz nawet pomyśleć, że jest intuicyjny i nie musisz go rozbijać, na przykład po prostu wiesz, że trójkąt pasuje do trójkąta i nie musisz przybliżać rozmiaru , policz krawędzie, .etc. To nie jest prawda, zrobiłeś to wszystko w swojej podświadomości, jedyną świadomą myślą, jaką miałeś, było to, że jest to trójkąt. Dokonano wielu milionów obliczeń, biorąc pod uwagę wizualną reprezentację, rozumiejąc, co to reprezentuje, rozumiejąc, jakie są poszczególne elementy, a następnie szacując ich odległości, a fakt, że dysponowałeś dużą bazą danych, z którą można było sondować, znacznie ułatwił.

Twój mózg nie jest binarny

Dane, na których pracuje Twój mózg, nie są binarne (o ile wiemy), nie są prawdziwe ani fałszywe, zawierają wiele stanów, których używamy do interpretacji danych, często również źle się miewamy, nawet jeśli postępujemy zgodnie z prawidłowymi proces, ponieważ dane często się zmieniają. Zaryzykowałbym przypuszczenie, że nasze mózgi funkcjonują bardziej jak komputer kwantowy, w którym bity są w przybliżonym stanie do momentu odczytania. Oznacza to, że jeśli nasz mózg w ogóle działa jak komputer, tak naprawdę nie jest znany.

Dlatego algorytm do pracy z danymi binarnymi nie będzie działał tak samo. Nie możesz ich porównać. W swojej głowie używasz pojęć do wykonywania, bogate typy danych, które przechowują znacznie więcej informacji, masz możliwość tworzenia łączy tam, gdzie nie są one wyraźnie zdefiniowane; po zobaczeniu trójkąta możesz pomyśleć o Ciemnej stronie osłony księżyca Pink Floyda.

wprowadź opis zdjęcia tutaj

Wracając do wykresu rozrzutu, nie ma powodu, dla którego nie można tego zrobić na komputerze za pomocą mapy bitowej i mierząc odległość od punktu w rosnących promieniach, aż do napotkania innego punktu. Jest to prawdopodobnie najbliższe przybliżenie człowieka. Prawdopodobnie będzie znacznie wolniej z powodu ograniczeń danych i ponieważ nasze mózgi niekoniecznie dbają o złożoność obliczeń i wybierają złożoną drogę do robienia rzeczy.

Nie byłoby O (1), a nawet O (n), jeśli n jest liczbą punktów, zamiast tego jego złożoność zależy teraz od maksymalnej liniowej odległości od wybranego punktu do granicy obrazu.

tl; dr

Twój mózg nie jest komputerem binarnym.


George Reith
źródło
8

zapominasz o jednym ważnym kroku: wykreślając wszystkie punkty na wykresie, na który patrzysz.

jest to z konieczności operacja O (n).

po tym komputer może użyć oprogramowania do rozpoznawania obrazów, aby znaleźć przybliżone punkty najbliżej środka, w taki sam sposób, jak ludzkie oko. Jest to najgorszy przypadek operacji O (sizeOfImage).

aby człowiek zrobił to samo, co komputer, pamiętaj, że komputer otrzymuje listę współrzędnych i może przeglądać tylko jedną z nich naraz.

maniak zapadkowy
źródło
1
Jeśli wybierzesz stałą „rozdzielczość”, możesz użyć algorytmu, który jest czasem O (log (rozdzielczość)) na punkt, aby wykreślić je i zidentyfikować wszystkie punkty, które są „bliskie” punktu zainteresowania. O (log (rozdzielczość)) jest niejasno analogiczne do faktu, że dokładne rysowanie punktów na papierze zajmuje więcej czasu niż wykonywanie go mniej dokładnie. Zauważ też, że zwiększenie rozdzielczości zwiększy koszt algorytmów na wszystkie punkty, aby wyeliminować punkty nie będące kandydatami, ale zmniejszy liczbę punktów nie najbliższych, które przetrwają eliminację.
supercat
7

Moja interpretacja pytania:

Nie wierzę, że to pytanie należy traktować w uproszczeniu jako zagadnienie złożoności geometrii obliczeniowej. Powinno to być lepiej rozumiane jako powiedzenie: dostrzegamy zdolność do znalezienia odpowiedzi w stałym czasie, kiedy możemy. To, co wyjaśnia tę percepcję, aż do tego wyjaśnienia i ludzkich ograniczeń, może również zrobić komputer.

O(1)O(losol(n))

Może to zostać wzmocnione przez prawa Webera-Fechnera , które mówią, że naszą percepcję należy mierzyć w skali logarytmicznej rzeczywistej miary fizycznej. Innymi słowy, postrzegamy raczej warianty względne niż absolutne. To jest na przykład, dlaczego natężenie dźwięku jest mierzone w decybelach.

O(losol(n))Oψ(losol(losol(n)))Oψ

Oψ(losol(losol(n))) który ze wszystkich praktycznych celów jest prawdopodobnie percepcyjnie nierozróżnialny od stałej, i koniecznie trzeba dodać trochę stałego czasu, aby rozpocząć proces rozpoznawania i potwierdzić wynik.

Biorąc pod uwagę ograniczenia fizjologiczne

Powyższy wniosek został podtrzymany przy rozważaniu etapów akwizycji obrazu.

OP starał się oddzielić budowę odpowiedniej struktury danych, „takiej jak czterokrotnie”, która jest amortyzowana w kilku zapytaniach.

Nie działa to w przypadku większości osób, które nie zapamiętują obrazu. Myślę, że obraz jest skanowany dla każdego zapytania, ale nie oznacza to skanowania wszystkich punktów: nie za pierwszym razem i nie w przypadku późniejszych zapytań.

T.sdozanT.sdozan

mOψ(losol(losol(m)))

2)27losol2)(27)

Bez znajomości rzeczywistych jednostek, które mają być użyte, pokazuje to po prostu, że najgorsza odmiana przetwarzania jest w tej samej kolejności, co inne operacje o stałym czasie. Dlatego całkiem naturalne jest, że postrzegany czas na znalezienie najbliższego punktu wydaje się stały. . . czy określamy najbliższy punkt, czy tylko zbiór najbliższych punktów.

O kontrprzykładach i możliwym rozwiązaniu

Oczywiście łatwo jest budować kontrprzykłady, które bardzo utrudniają określenie najbliższego punktu w oczach wśród niewielkiej grupy bliższych punktów. Właśnie dlatego OP prosi o algorytm, który szybko eliminuje większość punktów, z wyjątkiem tych najbliższych. Kwestia możliwej trudności wyboru między kilkoma bliskimi punktami jest poruszana w wielu odpowiedziach, przy czym paradygmatyczny przykład najbliższych punktów znajduje się prawie na okręgu wokół punktu odniesienia. Zazwyczaj prawa Webera-Fechnera wykluczają możliwość rozróżnienia niewielkich zmian odległości na wystarczająco dużych odległościach. Efekt ten może faktycznie zostać zwiększony przez obecność innych punktów, które - choć wyeliminowane - mogą zniekształcać postrzeganie odległości. Próbowanie zidentyfikowania najbliższego punktu będzie trudniejszym zadaniem, i może wymagać określonych kroków badania, takich jak użycie instrumentów, które całkowicie zniszczą poczucie ciągłego czasu. Wydaje się jednak, że wyraźnie wykracza poza zakres eksperymentów rozważanych przez PO, a zatem nie jest zbyt istotny.

Pytanie , na które należy odpowiedzieć , to pytanie faktycznie postawione przez PO, brzmi, czy istnieje sposób na wyeliminowanie większości punktów, z wyjątkiem ewentualnie pozostałych kilku, które wydają się mieć bardzo podobne odległości do punktu odniesienia.

O(losol(n))

Odrzucenie zamortyzowanego kosztu nie pozwala na rozwiązanie komputerowe, ponieważ należy przeanalizować wszystkie punkty. Podkreśla to zasadniczą różnicę w mocy obliczeniowej mózgu i percepcji człowieka: może on wykorzystywać obliczenia analogowe o właściwościach zupełnie innych niż obliczenia cyfrowe . Zazwyczaj ma to miejsce, gdy miliardy punktów nie są rozpoznawalne przez oko, które nie ma rozdzielczości, aby zobaczyć cokolwiek poza dużą chmurą o różnych odcieniach ciemności. Ale oko może wtedy skupić się na odpowiedniej mniejszej części i zobaczyć ograniczoną liczbę punktów zawierających odpowiednie punkty. Nie musi znać wszystkich punktów indywidualnie. Aby komputer zrobił to samo, musiałbyś nadać mu podobny czujnik, a nie dokładne współrzędne liczbowe każdego punktu. To jest zupełnie inny problem.

„Zwykła kontrola wizualna” jest pod pewnymi względami znacznie bardziej wydajna niż obliczenia cyfrowe. Wynika to również z fizyki czujników, a nie tylko z potencjalnie większej mocy obliczeniowej mózgu.

Babou
źródło
O(1)O(logn) O(1)O(1)O(logn)gdy rozwiązujesz zadanie wykraczające poza zwykłe rozpoznawanie percepcyjne, np. lokalizowanie danej liczby w graficznej reprezentacji zrównoważonej sterty binarnej z oznaczonymi węzłami. zwróć uwagę, że ograniczenia percepcyjne nie mają znaczenia, ponieważ sprawdzasz grafikę tylko lokalnie.
Collapsar
n
Oψ(losol(losol(n)))
4

Mieliśmy uczniów w egzaminach, którzy zapytani o to, jak szybko można posortować tablicę, twierdziliby, że komputery są głupie i potrzebują n * log (n) (lub gorzej), podczas gdy ludzie mogą to zrobić szybciej.

Odpowiedź mojego profesora zawsze brzmiała: podam listę 10.000 pozycji. Zobaczmy, czy możesz wymyślić metodę, która jest szybsza niż to, co zrobiłby komputer.

A potem: ile rdzeni przetwarzających jest zaangażowanych, gdy próbujesz znaleźć najbliższy punkt? Nie jesteś maszyną jednoprocesorową, masz sieć neuronową, która ma pewną elastyczność, jeśli chodzi o takie zadania.

Zane
źródło
1
Plus różne aspekty tego, co wiesz o danych i jakie zasoby masz dostępne, kiedy trzeba sortować. Na przykład, jeśli twoi koledzy muszą posortować coś, co nie mieści się całkowicie w pokoju, to są.
Thorbjørn Ravn Andersen
@ ThorbjørnRavnAndersen: miło jest zrozumieć, jak ważna jest złożoność przestrzeni „coś, co nie mieści się całkowicie w pokoju” 8 ^)
Zane
3

Uważam, że @ Patrick87 dał ci wskazówkę: twoje oczy i mózg są masowo równoległą maszyną obliczeniową. Niektórzy twierdzili, że nie wyjaśnia to problemu, ponieważ w przypadku dowolnie dużych problemów skończona liczba równoległych procesorów nie ma znaczenia.

Ale robi się tutaj: jak wielu sugeruje, twoje oczy (i mózg) mają ograniczoną zdolność do rozwiązania tego problemu; a to dlatego, że nie można zmieścić żadnej liczby punktów w zasięgu normalnego ludzkiego wzroku. Twoje oczy muszą być w stanie je rozróżnić na początek, a jeśli będzie ich zbyt wiele, będą tak blisko, że twoje oczy nie zauważą różnicy. Podsumowując: jest szybki dla wystarczająco dobrych punktów, które pasują do twojego normalnego wzroku, tj. Bardzo niewielu. W innych przypadkach zawiedzie.

Tak więc możesz rozwiązać ten problem w O (1) dla małych i prostych przypadków, które twój mózg może przetworzyć w mgnieniu oka. Poza tym nie może i dlatego nie jest nawet O ( cokolwiek ), ponieważ najprawdopodobniej zawiedzie.

carlosayam
źródło
1

Nikt nie wspomniał, że problem ten można rozwiązać bardzo szybko na komputerze z indeksem przestrzennym. Jest to odpowiednik wykreślenia punktów na obrazie, aby twoje oczy szybko zeskanowały i wyeliminowały większość punktów.

Istnieje bardzo dobry algorytm indeksowania wykorzystywany przez Google i inne osoby do znajdowania najbliższych punktów zwanych Geohash. http://en.wikipedia.org/wiki/Geohash .

Myślę, że to nawet zwiększy konkurencję na korzyść komputera. Nie byłem pod wrażeniem niektórych odpowiedzi wykorzystujących myślenie liniowe.

użytkownik3451435
źródło
Θ(n) Θ(lgn)
Chodzi o to, że indeks przestrzenny sprawia, że ​​jest on z grubsza tak łatwy, jak człowiek patrzy na ekran wypełniony kropkami.
reinierpost
1

Jeśli weźmiemy pod uwagę przypadek znalezienia najbliższych sąsiadów w zestawie punktowym n-wymiarów w przestrzeni euklidesowej, złożoność jest zwykle ograniczona przez liczbę wymiarów, gdy stają się one duże (tj. Większe niż rozmiar zbioru danych).

O(logre-2)n)

Problem znalezienia najbliższego punktu na węźle na wykresie ma wyrażenie euklidesowe, ilekroć wykres można osadzić w przestrzeni euklidesowej z wystarczająco małym zniekształceniem. Korzystając z listy przylegania z wagami, nadal musimy zbudować listę przylegania.

O(1)

użytkownik13675
źródło
-1

inne odpowiedzi są dobre, ale co powiesz na pytanie przeciwne zen, które rozciąga podstawowe rozumowanie / założenie pierwotnego pytania do skrajności, aby wykazać pewną wadę [ale jest również paradoksem u podstaw badań nad AI ]:

skoro potrafię myśleć ludzką inteligencją, dlaczego nie mogę stworzyć komputera, który myśli równie dobrze jak człowiek?

istnieje wiele sposobów odpowiedzi na twoje pytanie, ale w zasadzie nasze procesy myślowe i zdolności percepcyjne mózgu niekoniecznie są dostępne dla introspekcji, a introspekcja, którą do nich stosujemy, może być myląca. na przykład możemy rozpoznać obiekty, ale nie mamy sposobu na dostrzeżenie / wyjaśnienie quasi-algorytmicznego procesu, który na to pozwala. istnieje również wiele eksperymentów psychologicznych, które pokazują subtelne zniekształcenia w naszym postrzeganiu rzeczywistości, aw szczególności postrzeganiu czasu, patrz np . postrzeganie czasu .

naukowcy uważają, że ludzki mózg faktycznie stosuje algorytmy, ale działają one inaczej niż skomputeryzowane, a ponadto istnieje bardzo duża liczba procesów równoległych w mózgu za pośrednictwem sieci neuronowych , których nie można rozsądnie porównać z sekwencyjne algorytmy komputerowe. u ssaków znaczna część całej objętości mózgu jest przeznaczona na przetwarzanie wzrokowe.

innymi słowy, ludzki mózg jest pod wieloma względami wysoce zoptymalizowanymi komputerami wizualnymi, i w rzeczywistości pod wieloma względami ma możliwości, które przekraczają obecnie największe superkomputery na świecie, takie jak rozpoznawanie obiektów itp., a to z powodu wad (w porównaniu) w skonstruowanym przez człowieka oprogramowaniu / sprzęcie w porównaniu z biologią, która była przez wiele lat doskonalona / rozwijana / optymalizowana.

vzn
źródło
O(fa(n))
-2

Mówiąc ogólnie, rozwiązujesz dwa różne problemy i jeśli bierzesz udział w tej samej konkurencji, złożoność będzie wynosić O (1) dla was obu. Dlaczego? Uprośćmy sytuację - załóżmy, że masz linię z jednym czerwonym punktem i n zielonymi punktami. Twoim zadaniem jest znalezienie zielonego punktu, który jest najbliżej czerwonego punktu. Wszystko jest na wykresie. Teraz to, co robisz i co programujesz, jest w zasadzie takie samo - po prostu „odejdź” (w obu kierunkach) od czerwonego punktu i sprawdź, czy piksel, na który patrzysz, jest biały / czarny (tło) czy zielony. Teraz złożoność wynosi O (1).

Co ciekawe, niektóre metody prezentacji danych dają natychmiastowe odpowiedzi na niektóre pytania (O (1)). Podstawowy przykład jest niezwykle prosty - wystarczy policzyć białe piksele na czarnym obrazie (każda wartość piksela to 0 = czarny lub 1 = biały). Musisz tylko dodać wszystkie wartości pikseli - złożoność jest taka sama dla 1 białego piksela i dla 1000, ale zależy to od rozmiaru obrazu - O (m), m = image.width * image.height. Czy można to zrobić szybciej? Oczywiście wszystko, co musimy zrobić, to zastosować inną metodę przechowywania obrazów, która jest obrazem integralnym : wprowadź opis zdjęcia tutaj Teraz obliczamy wynik O (1) (jeśli masz już obraz całkowy obliczony). Innym sposobem jest po prostu przechowywanie wszystkich białych pikseli w tablicy / wektorze / liście / ... i po prostu policzenie ich rozmiaru - O (1).

cyriel
źródło
O(1)O(1)
@FrankW - więc jaka jest złożoność „odchodzenia”? Nie próbuję powiedzieć, że się mylisz, chcę tylko wiedzieć. Zliczanie rozmiaru tablicy / wektora / listy - ogólnie rozmiar tablicy jest stały, więc nie trzeba go liczyć, wektor - nie jestem pewien, powiedziałbym, że zależy to od implementacji (ale najprawdopodobniej w większości implementacji jest to tylko pole obiekt, więc nie trzeba go liczyć), lista - masz rację, to nie O (1) - mój błąd.
cyriel
kkO(#pjaxmils)