¿Cómo saber cuándo Big O es logarítmico?

Question

Mi pregunta surge de la publicación "Plain English Explanation of 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, quiero saber un método para determinarlo rápidamente en papel.

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

Answer 1

No estoy seguro de si esto es lo que quiere decir, pero ... la complejidad logarítmica generalmente surge cuando se trabaja con una estructura de datos extendida como un árbol binario balanceado, que contiene 1 nodo en la raíz, 2 hijos, 4 nietos, 8 bisnietos, etc. Básicamente en cada nivel, el número de nodos se multiplica por un factor (2) pero solo uno de ellos está involucrado 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) { ... } 

Cosas así son las firmas de complejidad logarítmica.

Answer 2

Master theorem generalmente funciona.

Answer 3

No es riguroso, pero tiene un algoritmo que básicamente divide el trabajo necesario a la mitad en cada iteración, luego tiene una complejidad logarítmica. El ejemplo clásico es la búsqueda binaria.

Answer 4

Si solo quiere saber logarítmico Big Oh, esté atento cuando sus datos se reduzcan a la mitad en cada paso de la recurrencia.

Esto se debe a que si está procesando datos que son 1/2 más grandes que el paso anterior, se trata de una serie infinita.

Answer 5

Aquí hay otra forma de decirlo.

Supongamos que su algoritmo es lineal en la cantidad de dígitos del tamaño del problema. Entonces, quizás tengas un nuevo algoritmo para factorizar un número grande, que puedas mostrar como lineal en el número de dígitos. Un número de 20 dígitos por lo tanto, toma el doble de tiempo para factorizar como un número de 10 dígitos utilizando su algoritmo. Esto tendría complejidad de registro. (Y valdría la pena algo para el inventor.)

Bisección tiene el mismo comportamiento. Se necesitan aproximadamente 10 pasos de bisección para cortar la longitud del intervalo en un factor de 1024 = 2^10, pero solo 20 pasos reducirán el intervalo en un factor de 2^20.

La complejidad del registro no siempre significa que un algoritmo sea rápido en todos los problemas. El factor lineal en frente del O (log (n)) puede ser grande. Por lo tanto, su algoritmo puede ser terrible en problemas pequeños, y no se vuelve útil hasta que el tamaño del problema sea apreciablemente grande para que otros algoritmos mueran una muerte exponencial (o polinómica).