tiempo de ejecución asintótica de la función de lista de árbol

Question

Tengo una función merge que lleva tiempo O(log n) combinar dos árboles en una sola, y una función de listToTree que convierte una lista inicial de elementos a los árboles únicos y repetidamente llamadas merge en cada par sucesivo de árboles hasta que solo quede un árbol.

firmas de funciones e implementaciones relevantes son los siguientes:

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 

Ésta es una versión ligeramente simplificada de ejercicio en 3.3 Estructuras de datos puramente funcional por Chris Okasaki.

De acuerdo con el ejercicio, ahora mostraré que listToTree toma O(n) vez. Lo cual no puedo. :-(

Hay trivialmente ceil(log n) llamadas recursivas a listToTreeR, lo que significa ceil(log n) llamadas a mergePairs.

El tiempo de ejecución de mergePairs depende de la longitud de la lista, y los tamaños de los árboles. La longitud de la lista es 2^h-1, y los tamaños de los árboles son log(n/(2^h)), donde h=log n es el primer paso recursivo, y h=1 es el último paso recursivo. Cada llamada a mergePairs por lo tanto lleva tiempo (2^h-1) * log(n/(2^h))

estoy teniendo problemas para tak seguir este análisis. ¿Alguien puede darme una pista en la dirección correcta?

Answer 1

Ya casi está allí. Usted ya conoce la expresión es

por lo que el único problema es la evaluación de esta suma. Uso de log (AB) = log A + log B y log 2 ^N = N tenemos

With help of calculators, podemos encontrar que X = O (2 ^m) = O (n), que se espera.

(Si desea calcular esto usted mismo, busque "Serie geométrica", o acerque la suma usando una integral.)