¿Es la complejidad O (log (n)) equivalente a O (sqrt (n))?

Una manera fácil de agarrar esto es que Iniciar sesión₂(NORTE) será un valor cercano al número de dígitos (binarios) de norte, tiempo sqrt (N) será un número que tiene la mitad del número de dígitos que norte tiene. O, para afirmar que con igualdad:

Iniciar sesión₂(N) = 2 log₂(raíz cuadrada (N))

Entonces necesitas tomar el logaritmo (!) De sqrt (N) para reducirlo al mismo orden de complejidad que Iniciar sesión₂(NORTE).

Por ejemplo, para un número binario con 11 dígitos, 0b10000000000 (= 2¹⁰), la raíz cuadrada es 0b100000, pero el logaritmo es solo 10.

Asumiendo natural logarithm (de lo contrario, simplemente multiplique por una constante), tenemos

lim {n->inf} log n / sqrt(n) = (inf / inf)

                        =  lim {n->inf} 1/n / 1/(2*sqrt(n)) (by L'Hospital)
                        =  lim {n->inf} 2*sqrt(n)/n
                        =  lim {n->inf} 2/sqrt(n)
                        =  0 < inf

Consulte https://en.wikipedia.org/wiki/Big_O_notation para obtener una definición alternativa de O(.) y así desde arriba podemos decir log n = O(sqrt(n)),

También compare el crecimiento de las funciones a continuación, log n siempre está delimitado por la parte superior sqrt(n) para todos n > 0.

No, no es equivalente.

@trincot dio una excelente explicación con un ejemplo en su respuesta. Estoy agregando un punto más. Tu profesor te enseñó que

any operation that halves the length of the input has an O(log(n)) complexity

También es cierto que

any operation that reduces the length of the input by 2/3rd, has a O(log3(n)) complexity
any operation that reduces the length of the input by 3/4th, has a O(log4(n)) complexity
any operation that reduces the length of the input by 4/5th, has a O(log5(n)) complexity
So on ...

Incluso es cierto para todas las reducciones de longitudes de la entrada por (B-1)/Bth. Entonces tiene una complejidad de O(logB(n))

N:B: O(logB(n)) medio B logaritmo basado en n

Utiliza Nuestro Buscador