Ближайшая пара точек (CLRS, стр. 1043): время разбивки отсортированного массива на два отсортированных массива.

Question

При поиске ближайшей пары точек за время O(nlgn) псевдокод для разбиения отсортированного списка на два отсортированных списка (CLRS 3rd ed pg 1043) выполняется за время O (n).

Тем не менее, это предполагает, что строка 4 выполняется в постоянное время, в которое мне трудно поверить (я бы предположил, что оно выполняется за O (lgn) время, если бы оно хранилось в виде двоичного дерева, что дает общее время выполнения O(nlgn),

Y - отсортированный массив, YL и YR - два новых подмассива. PL - это подмножество Y в случайном порядке, а YL - это то же самое подмножество, но в отсортированном порядке.

Где я ошибаюсь с моими рассуждениями?

Answer 1

Для простоты мы предполагаем, что список состоит из целых чисел, а не строк или целых чисел, которые могут сильно усложнить ситуацию.

Здесь необходимо рассмотреть два расчета:

1. для цикла: это работает на длину Y раз, который я предполагаю, N здесь
2. самая сложная часть - сравнение Y[i] с PL(примечание: сравнение двух чисел является постоянным, если мы считаем, что они имеют размер слова). Теперь доступ к Y[i] является постоянным, поскольку мы имеем дело с машинами произвольного доступа. Однако, чтобы сравнить его с массивом PL длины, скажем, k, потребуется k времени. Если это k очень мало и не зависит от размера входного массива Y, это в идеале было бы постоянным.

Чтобы написать его с большей точностью, вы должны учитывать время, необходимое для k сравнений (длина PL), и, следовательно, общее время этого псевдокода будет равно O(Nk). Но если предположения о том, что k является случайным и не зависит от N, верны, то это действительно O(N)

Answer 2

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

• Y[i], X[i], YL[i], XL[i], YR[i] а также XR[i] целые числа, соответствующие индексу ith-point (так что вам просто нужно сохранить некоторый глобальный массив, который, учитывая индекс, возвращает x или же y координат).
• PL[i] является логическим, true если i-я точка находится в левой части, false иначе.

На каждом шаге рекурсии вы можете вычислить PL[i] с помощью y координаты (O(n) время). Затем вы разделяете набор точек в двух наборах "влево" и "вправо", используя алгоритм из книги, заменяя линию if Y[i] in PL от if PL[Y[i]] (такой доступ O(1)Итак, в целом мы получаем O(n)).

Это имеет O(n) сложность времени и использование O(n) объем памяти.

Таким образом, ближайшая пара проблема решается таким образом в T(n) = O(n log n),