Почему я могу посмотреть на график и сразу же найти ближайшую точку к другой точке, но на программирование у меня уходит O (n) время?

122

Позвольте мне уточнить:

Учитывая диаграмму рассеяния некоторого заданного числа точек n, если я хочу мысленно найти ближайшую точку к любой точке на графике, я могу сразу игнорировать большинство точек на графике, сужая свой выбор до некоторого небольшого, постоянного числа точек поблизости ,

Тем не менее, в программировании, учитывая набор точек n, чтобы найти ближайшую точку к какой-либо из них, требуется проверка каждой другой точки, которая является временем.O(n)

Я предполагаю, что визуальное представление графика, вероятно, эквивалентно некоторой структуре данных, которую я не в состоянии понять; потому что при программировании путем преобразования точек в более структурированный метод, такой как дерево квадрантов, можно найти ближайшие точки к точкам в за времени или амортизировать времяn k log ( n ) O ( log n )knklog(n)O(logn)

Но до сих пор нет известных алгоритмов аммортизации (которые я могу найти) для поиска точек после реструктуризации данных.O(1)

Так почему же это представляется возможным при простом визуальном осмотре?

Ari
источник
36
Вы уже знаете обо всех точках и приблизительно где они находятся; «программные драйверы» для ваших глаз уже сделали тяжелую работу по интерпретации изображения. По вашей аналогии вы считаете эту работу «бесплатной», хотя на самом деле это не так. Если у вас уже была структура данных, которая разбивала точечные позиции на некие представления октодеревьев, вы могли бы сделать это намного лучше, чем O (n). Большая часть предварительной обработки происходит в подсознательной части вашего мозга, прежде чем информация достигнет сознательной части; никогда не забывайте, что в подобных аналогиях.
Ричард Тингл
20
Я думаю, что по крайней мере одно из ваших предположений не выполняется в целом. предположим, что все точки расположены на окружности с «небольшими» возмущениями, а 1 дополнительная точка P является центром окружности. Если вы хотите найти ближайшую точку к P, вы не можете отклонить ни одну из других точек на графике.
коллапсар
4
Потому что наш мозг действительно потрясающий! Звучит как дешевый ответ, но это правда. Мы действительно немного знаем о том, как работает наша (по-видимому, массивно параллельная) обработка изображений.
Карл Witthoft
7
Ну, в основном, ваш мозг использует пространственное разделение, а вы не замечаете. Тот факт, что это выглядит действительно быстро, не означает, что это постоянное время - вы работаете с некоторым конечным разрешением, и ваше программное обеспечение для обработки изображений разработано для этого (и может даже обрабатывать все это параллельно). Тот факт, что для предварительной обработки вы используете сотни миллионов маленьких процессоров, не влечет за собой - он просто выполняет сложную операцию на многих маленьких процессорах. И не забывайте про черчение на 2D-бумаге - оно должно быть как минимум . O ( n )O(1)O(n)
Luaan
9
Не уверен, что это уже упоминалось, но человеческий мозг работает совсем не так, как вычислительная система типа SISD von Neumann. Особенно уместным здесь является то, что, насколько я понимаю, человеческий мозг по своей природе параллелен, особенно когда речь идет об обработке сенсорных раздражителей: вы можете слышать, видеть и чувствовать одновременно несколько вещей и быть (грубо, в любом случае) осведомленными из всех их одновременно. Я концентрируюсь на написании комментария, но вижу свой стол, банку с газировкой, мою куртку, висящую на двери, ручку на моем столе и т. Д. Ваш мозг может проверить много точек одновременно.
Patrick87

Ответы:

115

Ваша модель того, что вы делаете мысленно, неверна. На самом деле, вы работаете в два этапа:

  1. Устраните все точки, которые находятся слишком далеко, за время.O(1)
  2. Измерьте точек, которые находятся примерно так же близко, во время .Θ ( м )mΘ(m)

Если вы играли в такие игры, как петанк (миски) или керлинг, это должно быть знакомо - вам не нужно исследовать объекты, которые находятся очень далеко от цели, но вам может потребоваться измерить ближайших соперников.

Чтобы проиллюстрировать эту точку, какая зеленая точка ближе всего к красной точке? (Только чуть более чем на 1 пиксель, но есть один, который ближе всего.) Чтобы упростить задачу, точки даже имеют цветовую маркировку по расстоянию.

облако точек

Эта картина содержит точек, которые находятся почти на круге, и всего зеленых точек. Шаг 1 позволяет исключить все, кроме около точек, но шаг 2 требует проверки каждой из точек. Не существует априорной оценки для .н 10 м м мm=10n10mmm

Физическое наблюдение позволяет сократить размер задачи от всего набора из точек до ограниченного набора кандидатов из точек. Этот шаг не является этапом вычисления, как обычно понимается, потому что он основан на непрерывном процессе. Непрерывные процессы не подвержены обычным представлениям о вычислительной сложности и, в частности, асимптотическому анализу.мnm

Теперь вы можете спросить, почему непрерывный процесс не может полностью решить проблему? Как это происходит с этими точками, почему мы не можем уточнить процесс, чтобы получить ?м = 1mm=1

Ответ в том, что я немного обманул: я представил набор точек, который состоит из почти ближайших точек и точек, которые находятся дальше. В общем, определение того, какие точки находятся в пределах точной границы, требует точного наблюдения, которое должно выполняться точка за точкой. Грубый процесс исключения позволяет исключить множество очевидных не кандидатов, но для простого перечисления оставшихся кандидатов требуется их перечисление.н - мmnm

Вы можете смоделировать эту систему в дискретном вычислительном мире. Предположим, что точки представлены в структуре данных, которая сортирует их по ячейкам в сетке, то есть точка сохраняется в списке для ячейки . Если вы ищете точки , которые находятся ближе всего к и ячейкам, содержащие этот момент содержит более одной другой точку, то достаточно проверить , содержащие клетки и 8 соседних клеток. Общее количество баллов в этих 9 ячейках равно . Эта модель учитывает некоторые ключевые свойства человеческой модели:( x , y ) ( x 0 , y 0 ) m(x,y)(x,y)(x0,y0)m

  • m потенциально неограничен - всегда возможен вырожденный худший случай, например, точек, лежащих почти на окружности.
  • Практическая эффективность зависит от выбора масштаба, соответствующего данным (например, вы ничего не сэкономите, если ваши точки на листе бумаги, а ваши ячейки имеют ширину 1 км).
жилль
источник
9
Более того, не все графики могут быть спроецированы на плоскость, так что евклидовы расстояния соответствуют расстояниям на графике (например, если веса ребер не образуют метрику).
Рафаэль
5
@ Рафаэль Я понял вопрос как о вычислительной геометрии, а не о теории графов, но на самом деле это дополнительная сложность.
Жиль
2
@ Жиль Готово . Я только что выучил термин вычислительная геометрия .
gerrit
2
Это может быть придиркой, я могу понять, что вы пытаетесь показать, но тот, кто страдает дальтонизмом, «выбирайте ближайший зеленый к красному», приводит к тому, что у многих возникает царапина на голове относительно того, какие точки есть какие. Просто подумайте о будущем - выбирайте любые другие цветовые комбинации, кроме красного / зеленого!
tpg2114
3
@ tpg2114 Не забывайте, что красный / зеленый не единственный тип дальтонизма. Показ его с помощью формы (или любого другого атрибута, кроме цвета) будет более содержательным, чем «любые другие сочетания цветов, кроме красного / зеленого».
Джонатан Ван Матре
42

Причина в том, что данные были помещены в «структуру данных», оптимизированную для этого запроса, и что время предварительной обработки при подготовке графика должно быть включено в ваши измеренные времена, которое пропорционально количеству точек, что дает O (n) сложность прямо там.

Если вы поместите координаты в таблицу, содержащую координаты X и Y каждой точки, вам потребуется гораздо больше умственных усилий для вычисления расстояний между точками, сортировки списка расстояний и выбора наименьшего.

В качестве примера запроса, который не работает хорошо визуально, можно посмотреть на ночное небо и - основываясь только на вашем виде и таблице координат каждой звезды - найти ближайшую звезду к Земле или какой астрологический знак имеет наименьшее расстояние между звезды, из которых он состоит. Здесь вам понадобится масштабируемая и поворачиваемая трехмерная модель, чтобы определить это визуально, когда компьютер посчитает, что это по существу та же проблема, что и ваш оригинал.

Турбьерн Равн Андерсен
источник
2
+1 - я прокручивал вниз, ища кого-то, кто делает именно это. Представление входящих данных важно - просто попробуйте найти медиану отсортированного списка по сравнению с несортированным!
облачные ноги
21

Этот вопрос начинается с ошибочной предпосылки. Вы просто думаете, что можете мысленно найти ближайшую точку в точке , но на самом деле, если не можете. Такое ощущение, что вы привыкли иметь дело с очень маленькими графами, но маленькие примеры могут вводить в заблуждение, когда мы имеем дело с асимптотической сложностью. Если вы попытаетесь сделать это с помощью точечной диаграммы с миллиардом точек, вы быстро обнаружите, что не можете сделать это за время.O ( 1 )O(1)O(1)

DW
источник
8
Представьте себе, что вы располагаете миллиард точек по кругу, но все они слегка возмущены, поэтому ваши точки образуют размытое кольцо. Чтобы найти точку, ближайшую к центру, на глаз, я не вижу, как вы могли бы сделать намного лучше, чем проверять все точки один за другим.
Ник Алджер
4
@NickAlger Так что это больше похоже O(numberOfPointsAboutTheSameDistanceFromTheTargetPointAsTheClosestPoint), что не обязательно связано с n. В любом случае, я думаю, что ответ на этот вопрос должен представить возможные структуры данных с точки зрения того, как человеческий разум воспринимает и запрашивает их. Просто сказать, что это не O (1) чувствует себя ... ленивым? неадекватный?
Dukeling
5
@Dukeling O (что-то) относится к худшему случаю. Если есть какие-то схемы, в которых человеческий мозг не может делать это в постоянное время, то это определенно не O (1). Если есть некоторый предел X, в котором человеческий мозг может обрабатывать X точек в постоянное время, но не может обрабатывать X * 2 точек вообще - тогда это не O (1).
Петерис
3
@Dukeling Он обязательно зависит от n, так как в худшем случае он равен n, и если вы дали n произвольных точек, вы должны ожидать, что это может быть невозможно сделать быстрее, чем операции C * n.
Петерис
2
@Peteris Я думаю, мы не согласны с тем, что значит «обязательно зависеть от n» и как определить ближайшую верхнюю границу.
Dukeling
15

Превосходство визуального осмотра зависит от важных помещений, которые не могут быть гарантированы в целом:

  • масштабирование : вы сосредотачиваетесь на графическом представлении интересующей области. это означает, что геометрия была уменьшена, чтобы соответствовать вашему полю зрения. в общем случае это уже требует времени для предварительной обработки.O(n)

  • считать : (см. комментарий Ника Алжера к ответу, данному DW), предположить, что количество очков превышает количество ваших клеток сетчатки - вы даже не определите все вовлеченные точки.

  • дисперсия : (см. комментарий Ника Алжера к ответу, данному DW), предполагают набор точек на регулярной (например, гексагональной) сетке, подвергаемой небольшим случайным возмущениям. если эти возмущения станут меньше, чем разрешение вашей сетчатки (или любой другой наложенной сетки), вам будет не только сложно определить фактическое минимальное расстояние, но и выбрать неправильные пары точек с высокой вероятностью.

Предполагая, что психические процессы включают некоторую растеризацию геометрического представления (вместо, скажем, матрицы расстояний), эти процессы не масштабируются произвольно с размером экземпляра задачи. другими словами, для общей настройки потребуется процедура выборки предварительной обработки, работающая в . при визуальном осмотре человека параметры этой предварительной обработки встроены в аппарат восприятия (количество клеток сетчатки, область сетчатки), что делает эту стадию обработки .O ( 1 )O(n)O(1)

коллапсар
источник
1
ОП вычленял визуальный осмотр всех точек, поскольку это должно быть сделано любой системой, которая учитывает их все. Я думаю, именно поэтому он рассматривает амортизированную сложность . С другой стороны, за исключением редких людей, большинство людей не будут помнить график от одного вопроса к другому. Кроме того, тот факт, что глаз использует растровое изображение, означает, что сканирование выполняется в постоянное время, а фокусировка с достаточной точностью на соответствующую часть является логарифмической. Небольшие вариации на больших расстояниях все равно не воспринимаются (см. Законы Вебера-Фехнера в моем ответе). O ( l o g ( n ) )O(n)O(log(n))
Бабу
Насколько я понимаю, OP учел для применения алгоритма, который вычисляет NN для всех точек в готовясь к повторным поискам позже. моя точка зрения скорее состояла в том, что ни одно растровое сканирование в постоянное время не будет обслуживать все проблемы, так как различия в расстояниях могут упасть ниже интервала сетки или может быть больше, чем количество точек сетки. фокусировка на соответствующей части в логарифмическом времени не дает цели для всех точек «почти» на круге с 1 точкой в ​​центре, так как все точки актуальны (хотя, возможно, я вас и неправильно понял). n O ( nO(n)nнO(nlogn)n
коллапсар
15
  1. Компьютер решает другую проблему. Требуется список точек, а не растровое изображение точек. Преобразование из списка в изображение, то есть «построение» точек, занимает O(n)время.

    Быстрый! Что ближе всего к (1,2):

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

    Намного сложнее, верно? Бьюсь об заклад, если бы я составил список вдвое дольше, вам пришлось бы выполнять вдвое больше работы.

  2. Вы не знаете, сколько работы ваш мозг делает. Вы не «просто знаете», какая точка ближе. Ваш мозг выполняет вычислительную работу, чтобы выяснить этот ответ и сделать его доступным. Мозг работает над каждой точкой параллельно, поэтому время завершения остается примерно одинаковым, но количество требуемой работы все еще увеличивается с увеличением количества точек.

Крейг Гидни
источник
13

По той же причине, когда вы смотрите на треугольник и знаете, что это треугольник, вы забываете о миллионах вычислений, которые делаете, не замечая этого.

Нейронные сети

По сути, вы - нейронная сеть, которая была обучена и загружена массами данных.

Возьмите игру сортировки детской формы в качестве примера:

введите описание изображения здесь

Когда ребенок впервые взаимодействует с этим, вероятно, он попытается вставить фигуры в неправильные отверстия, это потому, что он еще не тренировал свой мозг или не нашел достаточно данных для построения сетей. Они не могут делать предположения о краях, размере и т. Д., Чтобы определить, какая форма соответствует отверстию.

Это кажется очевидным для вас (я надеюсь), потому что вы построили эти связи, вы можете даже подумать, что они интуитивно понятны и вам не нужно разбивать их, например, вы просто знаете, что треугольник соответствует треугольнику, и вам не нужно приближаться к размеру , посчитать края, и т.д. Это неправда, вы сделали все это в своем подсознании, единственной сознательной мыслью, которую вы имели, было то, что это треугольник. Многие миллионы вычислений произошли из визуального представления, понимания того, что он представляет, понимания того, что представляют собой отдельные элементы, а затем оценки их расстояний, того факта, что у вас была большая база данных для опроса, это стало проще.

Ваш мозг не бинарный

Данные, над которыми работает ваш мозг, не являются двоичными (насколько нам известно), не являются истинными или ложными, в них содержится много состояний, которые мы используем для интерпретации данных, мы также часто ошибаемся, даже когда следуем правильному процесс, это потому, что данные часто меняются. Я рискнул бы предположить, что наш мозг функционирует намного больше, чем квантовый компьютер, где биты находятся в приблизительном состоянии до чтения. То есть, если наш мозг работает как компьютер вообще, это действительно неизвестно.

Следовательно, алгоритм для работы с двоичными данными не будет работать так же. Вы не можете сравнить два. В своей голове вы используете концепции для выполнения, богатые типы данных, которые содержат гораздо больше информации, у вас есть возможность создавать ссылки там, где они не определены явно; увидев треугольник, вы можете подумать о Темной стороне Лунного покрова Пинк Флойд.

введите описание изображения здесь

Возвращаясь к диаграмме рассеяния, нет причин, по которым вы не могли бы сделать это на компьютере, используя растровое изображение и измеряя расстояние от точки по увеличивающимся радиусам, пока не встретите другую точку. Возможно, это самое близкое к человеческому приближению. Вероятно, это будет намного медленнее из-за ограниченности данных и потому, что наш мозг не обязательно заботится о сложности вычислений и выбирает сложный маршрут для выполнения задач.

Это не будет O (1) или даже O (n), если n - количество точек, вместо этого его сложность теперь зависит от максимального линейного расстояния от выбранной точки до границы изображения.

ТЛ; др

Ваш мозг не бинарный компьютер.


Джордж Райт
источник
8

вы забываете один важный шаг: вычерчиваете все те точки на графике, на который вы смотрите.

это по необходимости операция O (n).

после этого компьютер может использовать программное обеспечение для распознавания изображений, чтобы находить приблизительные точки, расположенные ближе всего к центру, почти так же, как человеческий глаз. Это наихудший случай операции O (sizeOfImage).

чтобы человек делал то же самое, что и компьютер, помните, что компьютер получает список координат и может просматривать только один за один раз.

чокнутый урод
источник
1
Если выбрать постоянное «разрешение», можно использовать алгоритм, который представляет собой время O (log (разрешение)) на точку, чтобы построить их и идентифицировать все точки, которые «близки» к точке интереса. O (log (разрешение)) в некоторой степени аналогично тому, что для точного нанесения точек на бумаге требуется больше времени, чем для менее точного. Также обратите внимание, что увеличение разрешения увеличит стоимость алгоритмов для всех точек, чтобы исключить точки, не являющиеся кандидатами, но уменьшит количество не ближайших точек, оставшихся после исключения.
суперкат
7

Моя интерпретация вопроса:

Я не верю, что этот вопрос следует понимать упрощенно как проблему сложности вычислительной геометрии. Следует лучше понимать как высказывание: мы ощущаем способность находить ответ в постоянное время, когда можем. То, что объясняет это восприятие, и вплоть до этого объяснения и человеческих ограничений, может делать и компьютер.

O(1)O(log(n))

Это может быть подкреплено законами Вебера-Фехнера , в которых говорится, что наше восприятие должно измеряться в логарифмическом масштабе фактической физической меры. Другими словами, мы воспринимаем относительные вариации, а не абсолютные вариации. Именно поэтому, например, интенсивность звука измеряется в децибелах.

O(log(n))Oψ(log(log(n)))Oψ

Oψ(log(log(n))) что для всех практических целей, вероятно, неотличимо от постоянной с точки зрения восприятия, и к нему обязательно добавляется некоторое постоянное время, чтобы начать процесс распознавания и подтвердить результат.

С учетом физиологических ограничений

Приведенный выше вывод дополнительно подтверждается при рассмотрении этапов получения изображения.

ОП был осторожен, чтобы отделить построение правильной структуры данных, "такой как квадродерево", которая амортизируется по нескольким запросам.

Это не работает для большинства людей, которые не запоминают изображение. Я думаю, что изображение сканируется для каждого запроса, но это не подразумевает сканирование всех точек: не в первый раз и не для последующих запросов.

TscanTscan

mOψ(log(log(m)))

227log2(27)

Не зная фактических единиц измерения, которые будут использоваться, это просто показывает, что изменение для обработки в худшем случае того же порядка, что и другие операции с постоянным временем. Следовательно, вполне естественно, что воспринимаемое время нахождения ближайшей точки ощущается постоянным. , , определяем ли мы ближайшую точку или только набор более близких точек.

О контрпримерах и возможном решении

Конечно, легко создать контрпримеры, которые затрудняют определение ближайшей точки глазами из небольшого набора точек сближения. Вот почему ОП фактически запрашивает алгоритм, который быстро устраняет большинство точек, за исключением самых близких. Эта проблема возможной трудности выбора между несколькими близкими точками решается во многих ответах, причем пример парадигмальной точки ближайших точек находится почти на окружности вокруг контрольной точки. Как правило, законы Вебера-Фехнера не позволяют различать небольшие изменения расстояния на достаточно больших расстояниях. Этот эффект может на самом деле быть увеличен присутствием других точек, которые, хотя и устранены, могут исказить восприятие расстояний. Поэтому попытка определить ближайшую точку будет более сложной задачей, и вполне может потребовать специальных шагов исследования, таких как использование инструментов, которые полностью уничтожат ощущение постоянного времени. Но это явно выходит за рамки экспериментов, рассматриваемых ФП, и поэтому не очень актуально.

Вопрос , на который нужно ответить , - это вопрос, который фактически задает ФП, - есть ли способ устранить большинство точек, за исключением, возможно, оставшихся немногих, которые, кажется, имеют очень похожие расстояния до контрольной точки.

O(log(n))

Отказ от амортизированной стоимости не позволяет найти компьютерное решение, так как необходимо учитывать все моменты. Это подчеркивает существенное различие в вычислительной мощности мозга и человеческого восприятия: он может использовать аналоговые вычисления со свойствами, которые сильно отличаются от цифровых вычислений . Обычно это тот случай, когда миллиарды точек не различимы глазом, у которого нет разрешения видеть что-либо, кроме большого облака с различными оттенками темноты. Но глаз может затем сфокусироваться на соответствующей меньшей части и увидеть ограниченное количество точек, содержащих соответствующие. Он не должен знать все пункты в отдельности. Чтобы компьютер делал то же самое, вы должны были бы дать ему аналогичный датчик, а не точные числовые координаты каждой точки. Это совсем другая проблема.

«Простой визуальный контроль» в некоторых отношениях намного более эффективен, чем цифровые вычисления. И это также связано с физикой сенсоров, а не только с возможной большей вычислительной мощностью мозга.

Babou
источник
O(1)O(logn) O(1)O(1)O(logn)когда вы решаете задачу, превосходящую распознавание восприятия, например, нахождение заданного числа в графическом представлении сбалансированной двоичной кучи с помеченными узлами. обратите внимание, что ограничения восприятия не имеют значения, поскольку вы проверяете графику только локально.
коллапсар
n
Oψ(log(log(n)))
4

У нас были студенты на экзаменах, которые, когда их спросили, как быстро вы можете отсортировать массив, заявят, что компьютеры глупы и нуждаются в n * log (n) (или хуже), тогда как люди могут делать это быстрее.

Ответ моего профессора был всегда: я дам список из 10.000 предметов. Давайте посмотрим, сможете ли вы придумать метод, который быстрее, чем компьютер.

И потом: сколько процессорных ядер задействовано, когда вы пытаетесь найти ближайшую точку? Вы не однопроцессорная машина, у вас есть нейронная сеть, которая обладает некоторой гибкостью, когда дело касается таких задач.

Зейн
источник
1
Плюс различные аспекты того, что вы знаете о данных и какие ресурсы у вас есть, когда вам нужно отсортировать. Например, если вашим сокурсникам нужно отсортировать что-то, что не может полностью поместиться в комнате, в которой они находятся.
Турбьерн Равн Андерсен
@ ThorbjørnRavnAndersen: это хороший способ понять, насколько важна сложность пространства «что-то, что не может полностью уместиться в комнате» 8 ^)
Зейн
3

Я думаю, что @ Patrick87 дал вам подсказку: ваши глаза и мозг - это массивно параллельная вычислительная машина. Некоторые утверждали, что это не объясняет проблему, потому что для произвольно больших задач конечное число параллельных процессоров не имеет значения.

Но это действительно так: как намекают многие, ваши глаза (и мозг) имеют ограниченные возможности для решения этой проблемы; и это потому, что нельзя подходить к любому количеству точек в пределах нормального человеческого взгляда. Ваши глаза должны быть в состоянии различить их для начала, и если их слишком много, то они будут настолько близко, что ваши глаза не заметят разницы. Итог: это быстро для достаточно хороших точек, которые соответствуют вашему обычному зрению, то есть очень мало. В других случаях это не удастся.

Таким образом, вы можете решить эту проблему в O (1) для небольших и простых случаев, которые ваш мозг может обработать на одном дыхании. Помимо этого, он не может, и, следовательно, это даже не O ( что-нибудь ), потому что он, скорее всего, терпит неудачу.

carlosayam
источник
1

Никто не упомянул, что эта проблема может быть решена очень быстро на компьютере с пространственным индексом. Это эквивалентно построению точек на изображении, чтобы ваши глаза могли быстро сканировать и устранить большинство точек.

Существует очень хороший алгоритм индексации, используемый Google и другими, чтобы найти ближайшую точку (точки), называемую Geohash. http://en.wikipedia.org/wiki/Geohash .

Я думаю, что это будет даже до конкурса в пользу компьютера. Меня не впечатлили некоторые ответы, в которых использовалось линейное мышление.

user3451435
источник
Θ(n) Θ(lgn)
Дело в том, что пространственный индекс делает его примерно таким же простым, как и для человека, смотрящего на экран, усеянный точками.
reinierpost
1

Если мы рассмотрим случай нахождения ближайших соседей в наборе точек n-измерений в евклидовом пространстве, сложность, как правило, ограничивается количеством измерений по мере того, как оно становится большим (т.е. больше, чем размер набора данных).

O(logd2n)

Проблема нахождения ближайшей точки к узлу в графе имеет евклидово выражение всякий раз, когда граф может быть встроен в евклидово пространство с достаточно малым искажением. И используя список смежности с весами, нам все еще нужно построить список смежности.

O(1)

user13675
источник
-1

другие ответы хороши, но как насчет встречного вопроса о дзен, который растягивает основные рассуждения / предпосылку исходного вопроса до крайностей, чтобы показать некоторую ошибочность [но также является парадоксом в основе исследований ИИ ]:

если я могу думать с человеческим интеллектом, почему я не могу создать компьютер, который мыслит так же, как человек?

Есть несколько способов ответить на ваш вопрос, но в основном наши мыслительные процессы и способности восприятия мозга не обязательно доступны для самоанализа, и самоанализ, который мы действительно применяем к ним, может вводить в заблуждение. например, мы можем распознавать объекты, но у нас нет способа воспринимать / объяснять квазиалгоритмический процесс, который позволяет это сделать. также есть много психологических экспериментов, которые показывают, что есть тонкие искажения в нашем восприятии реальности и в частности восприятии времени, см., например, восприятие времени .

Ученые обычно полагают / предполагают, что человеческий мозг на самом деле использует алгоритмы, но они функционируют не так, как компьютеризированные, а также существует очень большое количество параллельной обработки, выполняемой в мозге через нейронные сети, которую нельзя сравнивать разумно с последовательные компьютерные алгоритмы. у млекопитающих значительная часть всего объема мозга отводится визуальной обработке.

Другими словами, человеческий мозг во многих отношениях является высокооптимизированными визуальными компьютерами, и они действительно во многих отношениях обладают способностью, которая превосходит величайшие в настоящее время суперкомпьютеры в мире, такие как распознавание объектов и т. д., и это связано с недостатками (в сравнении). в программно-аппаратных средствах, созданных человеком, по сравнению с биологией, которая была тщательно настроена / усовершенствована / оптимизирована в течение миллионов лет.

ВЗН
источник
O(f(n))
-2

Вообще говоря, вы решаете две разные задачи, и если вы соревнуетесь в одном и том же соревновании, сложность будет равна O (1) для вас обоих. Почему? Давайте сделаем ситуацию немного проще - предположим, что у вас есть линия с одной красной точкой и n зелеными точками. Ваша задача - найти зеленую точку, которая ближе всего к красной точке. Все на графике. Теперь то, что вы делаете, и то, что делает ваша программа, в основном одно и то же - просто «уйдите» (в обоих направлениях) от красной точки и проверьте, является ли пиксель, на который вы смотрите, белым / черным (фон) или зеленым. Теперь сложность O (1).

Что интересно, некоторые методы представления данных дают ответы на некоторые вопросы сразу (O (1)). Основной пример очень прост - просто посчитайте белые пиксели на черном изображении (каждое значение пикселя равно 0 = черный или 1 = белый). Что вам нужно сделать, это просто добавить все значения пикселей - сложность одинакова для 1 белого пикселя и для 1000, но это зависит от размера изображения - O (м), m = image.width * image.height. Можно ли сделать это быстрее? Конечно, все, что нам нужно сделать, это использовать другой метод хранения изображений, который является целым изображением : введите описание изображения здесь теперь вычисляем результат O (1) (если у вас уже есть целое изображение). Другой способ - просто сохранить все белые пиксели в массиве / vector / list / ... и просто посчитать их размер - O (1).

Cyriel
источник
O(1)O(1)
@FrankW - так в чем же сложность "уходить"? Я не пытаюсь сказать, что вы не правы, я просто хочу знать. Подсчет размера массива / вектора / списка - обычно размер массива является постоянным, поэтому нет необходимости считать его, вектор - я не уверен, я бы сказал, что это зависит от реализации (но, скорее всего, в большинстве реализаций это просто поле объект, так что нет необходимости считать его), список - вы правы, это не O (1) - моя ошибка.
Сириэль
kkO(#pixels)