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

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

алгоритм от CLRS pg 1043

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

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

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

max_max_mir, в 05:48 (источник)

2 ответа

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

    Есть два расчета, чтобы рассмотреть здесь:

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

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

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

    • Y[i], X[i],YL[i],XL[i], YR[i]и XR[i]являются целыми числами, соответствующими индексу ith-point (поэтому вам просто нужно сохранить некоторый глобальный массив, который, учитывая индекс, возвращает координату xory).
    • 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).