¿Por qué la complejidad temporal del siguiente código O (logn)?

Depende de cómo defina su [matemática] n [/ matemática].

En este contexto, diría que [math] n [/ math] significa el número para el cual el algoritmo encuentra el reverso en representación decimal. Esto significa que el número tiene aproximadamente [math] log_ {10} (n) [/ math] dígitos, para cada dígito hay un número constante de operaciones, lo que lleva a [math] O (log (n)) [/ math] complejidad.

Eso sí, no es así como cualquier informático teórico, salvo algunos casos especiales, definiría [matemáticas] n [/ matemáticas]. Se define como el número de bits necesarios para representar el número. Esto significa que el tamaño de entrada es en realidad [matemática] m = log_2 (n) [/ matemática] y, por lo tanto, conduce a [matemática] O (m) [/ matemática] como la complejidad del tiempo, desde el punto de vista de la teoría de la complejidad.

Si tomamos la definición anterior de [matemática] n [/ matemática], comprobar si es primo se vuelve trivial en el tiempo polinómico. Incluso la factorización no sería difícil en el tiempo polinómico. Puedes ver por qué quería presentar la última definición.

Volvamos a lo básico:

¿Qué estamos haciendo cuando buscamos la complejidad big-O?

Estamos tratando de averiguar cuánto tiempo se ejecutará algún código dependiendo de su entrada.

Usualmente usamos la letra minúscula n para decir ‘el tamaño de la entrada’, porque el tiempo de ejecución de muchos algoritmos depende del tamaño de la entrada.

Cuando la complejidad es O (n), significa que el tiempo de ejecución del código es proporcional a la longitud de la entrada.

Ejemplo: encontrar el máximo de alguna matriz sin clasificar. En el peor, tendremos que mirar todos los números uno tras otro.

Cuando la complejidad es O (log (n)) significa que el tiempo de ejecución es proporcional al número de dígitos cuando se escribe la longitud de la entrada (log significa: encastrar los dígitos, el pequeño número que a veces aparece debajo del registro significa que base, dice si estamos contando dígitos de base 10, dígitos binarios, etc.).

Ejemplo: encontrar el máximo en una matriz ordenada de enteros. Para 1000 enteros se puede hacer en log (1000), que son 10 pasos en la base 2 usando la búsqueda dicotómica.

En el código mostrado, el tiempo de ejecución es proporcional al número de dígitos del número en la entrada. De ahora en adelante es definitivamente O (log). Que es un registro de base 10 es irrelevante para la complejidad.

Como última nota, si esto se implementa utilizando un ajuste de número normal en los registros del procesador, nunca será muy largo, en el peor de los 20 pasos, en el peor de los enteros de 64 bits.