Нет.
Предположим, что это возможно, с помощью алгоритма f мы покажем, что можем сортировать массив с O(n*logn/loglogn) сложностью по времени.
sort array A of length n:
(1) Create an 2-3 tree of size n, with no importance to keys. let it be T.
(2) store all pointers to nodes in T in a second array B.
(3) for each i from 0 to n:
(3.1) f(B[i],A[i]) //modify the tree: pointer: B[i] new value: A[i]
(4) extract elements from T back to A inorder.
правильность:
После каждогоактивация f дерево легально.После завершения активации f на всех элементах T и на всех элементах A дерево является допустимым и содержит все элементы.Таким образом, извлекая элементы из A, мы получаем обратно отсортированный массив.
сложность:
(1) Создание дерева [неважно, какие ключи мы ставим] равно O(n) мыможет поставить 0 во всех элементах, не имеет значения
(2) итерация T и создание B - это O(n)
(3), активация f - O(logn/loglogn), вызывая таким образомэто n раз равно O(n*logn/loglogn)
(4) извлечение элементов - это просто обход: O(n)
Таким образом: общая сложность составляет O(n*logn/loglogn)
Но сортировка - это проблема Omega(nlogn)с алгоритмами сравнения на основе.противоречие.
Заключение : желаемое f не существует.