Ближайшая пара точек грубой силы; Почему O (n^2)?

Я чувствую себя глупо задавать этот вопрос, но ...Ближайшая пара точек грубой силы; Почему O (n^2)?

Для «ближайшей пары точек» задач (см this, если не знакомы с ним), почему это наихудшее временем работы алгоритма перебора O (N^2)?

Если n = 4, то в пространстве поиска может быть только 12 возможных пар точек, если мы также рассмотрим сравнение двух точек с любого направления. Если мы не сравним две точки дважды, тогда это будет 6.

O (n^2) не соответствует мне.

источник

2017-01-17 user3407764

Как насчет 'n = 3'? А как насчет 'n = 5'? – arekolek

Число шагов пропорционально O (n^2), они не обязательно должны быть равны. – Lee

Фактическое количество сравнений: n*(n-1)/2. Это равно n^2/2-n/2. Но, в примечаниях с большими О, вас беспокоит только доминирующий термин. При очень больших значениях n термин -n/2 становится менее важным, как и коэффициент 1/2 на сроке n^2. Итак, мы просто говорим, что это O(n^2).

Нотация Big-O не предназначена для точной формулы времени и количества шагов. Это только дает вам порядок сложности/времени, чтобы вы могли понять, как он масштабируется для больших входов.

источник

2017-01-17 19:49:32

И причина, по которой мы не заботимся о коэффициенте, состоит в том, что мы всегда можем купить/построить компьютер, который будет быстрее или медленнее с постоянным коэффициентом. Или мы можем быть гораздо более терпеливыми. :) – biziclop

Отличная точка. Кроме того, вы можете легко получить коэффициент 2 разницы между хорошей реализацией и плохой реализацией алгоритма. –

В большом-O записи, вы можете факторизовать умноженные константы, так что:

O(k*(n^2)) = O(n^2)

Идея заключается в том, что константа (1/2 в примере OP, поскольку сравнение расстояния отражательное) не делает действительно расскажут нам что-нибудь новое о сложности. Он по-прежнему становится больше с квадратом входа.

источник

2017-01-17 19:45:02 danh

В варианте алгоритма с грубой силой вы сравниваете все возможные пары точек. Для каждого из n очков у вас есть (n - 1) другие очки для сравнения, и если мы возьмем каждую пару, когда закончим с (n * (n - 1))/2 сравнениями. Пессимистическая сложность O(n^2) означает, что количество операций привязано к k * n^2 для некоторой константы k. Нотация Big O не может указать точное количество операций, но функция, пропорциональная которой размер данных (n) увеличивается.

источник

2017-01-17 19:47:32 Ardavel

Применяя грубую силу, мы вынуждены проверять все возможные пары. Исходя из N точек, для каждой точки есть N-1 других точек, для которых нам нужно рассчитать расстояние. Таким образом, сумма возможных расстояний вычисляется = N точек * N-1 других точек. Но в процессе мы удвоили подсчитанные расстояния. Расстояние между А до В остается, рассчитывается ли А-В или В-А. Следовательно, N * (N-1)/2. Следовательно, O (N^2).

источник

2017-01-17 19:50:59 Abhi7950

Ближайшая пара точек грубой силы; Почему O (n^2)?

ответ

Смежные вопросы