¿Cómo saber cuando Big O es logarítmica?

Question

Mi pregunta surge del poste "Inglés Simple Explicación de Big O" . No sé el significado exacto de la complejidad logarítmica. Sé que puedo hacer una regresión entre el tiempo y el número de operaciones y calcular el valor X-cuadrado, y determinar así la complejidad. Sin embargo, me gustaría saber un método para determinar rápidamente en el papel.

¿Cómo se determina la complejidad logarítmica? ¿Hay algunos buenos puntos de referencia?

Answer 1

No estoy seguro si esto es lo que quieres decir, pero ... complejidad logarítmica por lo general surge cuando se trabaja con una estructura de datos desplegada como un árbol binario equilibrado, que contiene 1 nodo en la raíz, 2 niños, 4 nietos, 8 bisnietos, etc. Básicamente en cada nivel el número de nodos se multiplica por un factor (2), pero sigue siendo sólo una de ellas está implicada en la iteración. O, como otro ejemplo, un bucle en el que el índice se duplica en cada paso:

for (int i = 1; i < N; i *= 2) { ... }

Ese tipo de cosas son las firmas de complejidad logarítmica.

Answer 2

No es rigurosa, pero que han un algoritmo que se divide esencialmente el trabajo necesario para ser hecho a la mitad en cada iteración, entonces usted tiene complejidad logarítmica. El ejemplo clásico es la búsqueda binaria.

Answer 3

teorema Maestro por lo general funciona.

Answer 4

Si lo que desea saber sobre logarítmica grande Oh, estar al acecho para cuando se corta por la mitad sus datos cada paso de la recurrencia.

Esto se debe a que si está procesando datos que es medio tan grande como el paso previo a ella, es una serie infinita.

Answer 5

Aquí es otra manera de decirlo.

Supongamos que su algoritmo es lineal en el número de dígitos de la magnitud del problema. Por lo tanto, tal vez usted tiene un nuevo algoritmo para factorizar un número grande, que se puede demostrar que es lineal en el número de dígitos. Un número 20 dígitos toma de ese modo el doble de tiempo para factorizar como un número de 10 dígitos mediante su algoritmo. Esto tendría la complejidad de registro. (Y valdría la pena algo por el inventor.)

bisección tiene el mismo comportamiento. Se tarda aproximadamente 10 pasos de bisección para cortar la longitud de intervalo por un factor de 1,024 = 2 ^ 10, pero sólo 20 pasos cortará el intervalo por un factor de 2 ^ 20.

Registro complejidad no siempre significa que un algoritmo es rápido en todos los problemas. El factor lineal frente al O (log (n)) puede ser grande. Por lo que su algoritmo puede ser terrible en pequeños problemas, que no forman útil hasta el tamaño del problema es apreciablemente más grande que otros algoritmos mueren una muerte exponencial (o polinómica).