Notación asintótica: ¿n (log n) (log n) se simplifica?

Question

Si tengo un algoritmo que toma n log n pasos (por ejemplo, heapsort), donde los pasos toman log n time (por ejemplo, comparación / intercambio de " big " enteros en el rango de 0 a n -1), cuál es el límite asintótico para todo el proceso.

Obviamente podemos decir " n (log n) (log n) " ;, pero me cuesta mucho convencerme de que no puedo simplificar esto a " n log n " ;. Al mismo tiempo, me cuesta mucho justificar el instinto que insiste en que puedo.

¿Mi instinto simplemente está mal en esto?

EDIT

Parece que mi simple ejemplo para evitar complicar el problema lo ha complicado. Oh bien.

La verdadera razón de la pregunta es que a menudo tengo un algoritmo estándar con una complejidad conocida, pero implementado usando diferentes contenedores subyacentes, de modo que los pasos individuales son O (log n) en lugar de O (1). Por ejemplo, el algoritmo de minimización del autómata Hopcrofts es O (n log n), pero si comienza a usar contenedores de árbol binario para los estados, transiciones y resultados intermedios, los pasos se convierten en O (log n): el O (n log n) es ya no es válido porque la suposición de accesos O (1) no es válida.

Aún así, las personas afirmarán que hay n estados ym transiciones, pero nym tienden a estar relacionadas linealmente para los autómatas, suponiendo que el número de anotaciones de transición es constante y que los autómatas son más o menos deterministas.

No me he preocupado demasiado por esto en el pasado, los casos con los que trabajo no son muy grandes. Pero, bueno, estoy haciendo una refactorización importante de mi código de autómatas, y pensé que bien podría hacer las matemáticas correctamente para algunos algoritmos clave a medida que avanzo.

EDIT

También estoy cada vez más convencido de que " n (log n) (log n) " está mal.

Si a es O (b log b) donde b es O (log c), ¿qué es a en términos de c?

Answer 1

Aquí hay una prueba por contradicción:

Digamos que una función f (n) = n (log n) (log n). Supongamos que creemos que también es theta (n log n), por lo tanto, en otras palabras, hay una a para la que f (n) & Lt; = a * n log n se cumple para n grande.

Ahora considere f (2 ^ (a + 1)):

f (2 ^ (a + 1)) = 2 ^ (a + 1) * log (2 ^ (a + 1)) * log (2 ^ (a + 1)) = 2 ^ (a + 1 ) * log (2 ^ (a + 1)) * (a + 1), que es claramente más grande que a * 2 ^ (a + 1) * log (2 ^ (a + 1)), y tenemos una contradicción . por lo tanto, f (n) no es una función n log n.

Answer 2

En general, no puede multiplicar complejidades como esta: para la ordenación del montón, N indica el número de elementos en el montón, mientras que para los enteros grandes, N probablemente indica el límite superior de los posibles valores. En general, estos no tienen que estar relacionados, por lo que es más bien N log N log M (donde M es el rango que pueden tomar los elementos).

En una aplicación específica, lo más probable es que los enteros grandes sigan alguna distribución específica. Por ejemplo, se puede saber que todos están por debajo de 10 ^ 20. Si es así, las operaciones de comparación toman tiempo constante (determinado por un límite superior de 10 ^ 20). Entonces, log M también es constante, y toda la complejidad está en O (N log N).

Answer 3

No podrá reducir n (log n) (log n) a n (log n) simplemente porque eso no es una reducción por un factor constante.

¿Qué hay de malo con 2^<=> ?

Answer 4

Bien, la medida de complejidad general de un programa es la siguiente:

  

Complejidad O (f (n)) significa que existe c, de modo que el número de los pasos correspondientes de la máquina Turing antes de que termine no sea mayor que c * f (n), donde n es la longitud de entrada.

En esta definición, todo se tiene en cuenta, porque los números enteros pueden ser arbitrariamente grandes, y las operaciones aritméticas en ellos también aumentarían la función en O (n).

Pero si estuviéramos programando máquinas de Turing directamente, su pregunta no habría surgido. En el mundo real preferimos abstraer. Mientras todavía calculamos & Quot; pasos & Quot; que son necesarios para ejecutar el programa, asumimos que ciertas operaciones toman un paso . Suponemos que por diferentes razones:

• Puede parecerse al trabajo real de la CPU, donde cada suma de enteros de 32 bits es de hecho un paso (y existen algoritmos que realmente abusan de él, por ejemplo, " dominadores de verificador de bits ") .
• Comparamos diferentes algoritmos en el mismo dominio (por ejemplo, comparando clasificaciones de matriz midiendo el número de comparaciones).

En este caso (su primera EDICIÓN), si desea concretar su medida de complejidad, simplemente multiplique las funciones bajo O. Si lo que pensaba dar un paso ahora considera dar pasos O (log N), entonces el La cantidad de pasos concretados aumenta en un factor de O (log N). Por lo tanto, la complejidad total es O (N log N log N).

---

En cuanto a su segunda EDICIÓN, es una situación diferente. Deje que su algoritmo sea una complejidad de O (n log N). Pero usted sabe que la entrada consta de M números, cada uno de log K dígitos, por lo que `N = O (M log K) (necesitamos tener en cuenta los separadores, etc.). Es matemáticamente correcto escribir la complejidad general como O (M * log K * (log M + log log K)), por lo que no hay ningún problema aquí. Pero generalmente extraemos detalles innecesarios para encontrar una base común para comparar diferentes algoritmos.