Время построения неявного Treap за время O(n) ⇐ JAVA

[Anonymous]

У меня есть два алгоритма для построения неявности из массива, один из них непрерывно объединяет
Вот так:

Код: Выделить всё

public Node nlognConvertToTreap(int[] arr){
Node node = Node.EMPTY_NODE;
for (int x : arr) node = merge(node, new Node(x));
return node;
}

Другой стиль — «разделяй и властвуй», например:

Код: Выделить всё

public Node efficientConvertToTreap(int[] arr){
return divideAndConquer(arr, 0, arr.length-1);
}

private Node divideAndConquer(int[] arr, int left, int right){
if (left == right) return new Node(arr[left]);
int mid = (left+right)/2;

return merge(divideAndConquer(arr, left, mid), divideAndConquer(arr, mid+1, right));
}`

Я знаю, что первый из них требует времени nlogn,
подход с разделениемANDConquer должен использовать O(N), поскольку он удовлетворяет рекурсии
T(n) = 2T( n/2) + O(logn).
Моя реализация merge() рекурсивная, я подсчитал количество вызовов слияния в каждой реализации. Для n = 2^20 количество вызовов слияния в реализации nlogn должно быть примерно в 20 раз больше. Однако я вижу только четырехкратное улучшение. Может ли кто-нибудь помочь мне понять проблему с моим анализом/реализацией.

Подробнее здесь: https://stackoverflow.com/questions/785 ... in-on-time