Асимптотическое время выполнения функции списка к дереву

Question

У меня есть функция merge, которая объединяет два дерева в одно время O(log n), и функция listToTree, которая преобразует начальный список элементов в одноэлементные деревья и неоднократно вызывает merge для каждой последующей пары деревья, пока не останется только одно дерево.

Подписи функций и соответствующие реализации следующие:

merge :: Tree a -> Tree a -> Tree a --// O(log n) where n is size of input trees
singleton :: a -> Tree a            --// O(1)
empty :: Tree a                     --// O(1)
listToTree :: [a] -> Tree a         --// Supposedly O(n)

listToTree = listToTreeR . (map singleton)

listToTreeR :: [Tree a] -> Tree a
listToTreeR []     = empty
listToTreeR (x:[]) = x
listToTreeR xs     = listToTreeR (mergePairs xs)

mergePairs :: [Tree a] -> [Tree a]
mergePairs []       = []
mergePairs (x:[])   = [x]
mergePairs (x:y:xs) = merge x y : mergePairs xs

Это слегка упрощенная версия упражнения 3.3 в «Чисто функциональных структурах данных» Криса Окасаки.

В соответствии с упражнением я покажу, что listToTree занимает O(n) время. Что я не могу. : - (

Есть тривиальные ceil(log n) рекурсивные вызовы listToTreeR, что означает ceil(log n) вызовы mergePairs.

Время выполнения mergePairs зависит от длины списка и размеров деревьев. Длина списка 2^h-1, а размеры деревьев log(n/(2^h)), где h=log n - первый рекурсивный шаг, а h=1 - последний рекурсивный шаг. Таким образом, каждый вызов mergePairs занимает время (2^h-1) * log(n/(2^h))

У меня проблемы с дальнейшим анализом. Кто-нибудь может дать мне подсказку в правильном направлении?

Answer 1

Это почти там. Вы уже знаете, выражение

поэтому единственная проблема - оценить эту сумму. Используя log (AB) = log A + log B и log 2 ^N = N, мы имеем

С помощью калькуляторов мы можем обнаружить, что X = O (2 ^m ) = O (n), что ожидается.

(Если вы хотите вычислить это самостоятельно, выполните поиск по «Геометрическому ряду» или приблизьте сумму с помощью интеграла.)