algorithm - resueltos - por que es importante el analisis de algoritmos

Significado de lg*N en el análisis algorítmico

Question

Actualmente estoy leyendo sobre análisis algorítmico y leo que cierto algoritmo (unión rápida ponderada con compresión de ruta) es de orden N + M lg * N. Aparentemente, aunque esto es lineal porque lg * N es una constante en este universo. A qué operación matemática se está haciendo referencia aquí. No estoy familiarizado con la notación lg * N.

Answer 1

La definición recursiva de lg * n por Jason es equivalente a lg * n = m cuando 2 II m <= n <2 II (m + 1) donde
2 II m = 2 ^ 2 ^ ... ^ 2 (exponenciación repetida, m copias de 2)
Es la doble notación de flecha hacia arriba de Knuth. Así
lg * 2 = 1, lg * 2 ^ 2 = 2, lg * 2 ^ {2 ^ 2} = 3, lg * 2 ^ {2 ^ {2 ^ 2}} = 4, lg * 2 ^ {2 ^ { 2 ^ {2 ^ 2}}} = 5.
Por lo tanto, lg * n = 4 para 2 ^ {16} <= n <2 ^ {65536} . La función lg * n se aproxima al infinito extremadamente lentamente. (Más rápido que un inverso de la función A (n, n) de Ackermann que involucra n-2 flechas arriba).

Stephen

Answer 2

Supongo que está hablando del algoritmo analizado en la diapositiva 44 de esta conferencia: http://www.cs.princeton.edu/courses/archive/fall05/cos226/lectures/union-find.pdf

Donde dicen que "lg * N es una constante en este universo", creo que no están siendo completamente literales. lg * N parece aumentar con N según su tabla en el lado derecho de la diapositiva; simplemente crece a una velocidad tan lenta que no se puede considerar mucho más (N = 2 ^ 65536 -> log * n = 5). Como tal, parece que están diciendo que puedes ignorar el log * N como una constante porque nunca aumentará lo suficiente como para causar un problema.

Aunque podría estar equivocado. Así es simplemente como lo leo.

edit: podría ser útil tener en cuenta que para esta ecuación están definiendo "lg * N" para que sea 2 ^ (lg * (N-1)). Lo que significa que un valor N de 2 ^ (2 ^ (65536)) [un número mucho mayor] daría lg * N = 6, por ejemplo.

Answer 3

lg es "LOG" o exponencial inverso. Normalmente, lg se refiere a la base 2, pero para el análisis algorítmico, la base generalmente no importa.

Answer 4

lg n se refiere a la base de registro n. Es la respuesta a la ecuación 2 ^ x = n. En el análisis de complejidad de Big O, la base para registrar es irrelevante. Los poderes de 2 surgen en CS, por lo que no es de extrañar que si tenemos que elegir una base, será la base 2.

Un buen ejemplo de dónde surge es un árbol completamente binario de altura h, que tiene 2 ^ h-1 nodos. Si permitimos que n sea el número de nodos, esta relación es que el árbol es la altura lg n con n nodos. El algoritmo que atraviesa este árbol toma como máximo lg n para ver si un valor está almacenado en el árbol.

Como es de esperar, wiki tiene gran información adicional.

Answer 5

Logarithm se denota por log o lg. En su caso, supongo que la interpretación correcta es N + M * log (N).

EDITAR: La base del logaritmo no importa cuando se realiza un análisis de complejidad asintótica.

Answer 6

Las respuestas dadas aquí hasta ahora están equivocadas. lg* n (leído "log star") es el logaritmo iterado. Se define como recursivamente como

 0 if n <= 1
lg* n =
1 + lg*(lg n) if n > 1

Otra forma de verlo es la cantidad de veces que tiene que iterar el logaritmo antes de que el resultado sea menor o igual a 1.

Crece extremadamente lentamente. Puede leer más en Wikipedia que incluye algunos ejemplos de algoritmos para los cuales lg* n aparece en el análisis.