¿Qué es el crecimiento logarítmico en notación asintótica?

Answer 1

El crecimiento del logaritmo se puede establecer de la siguiente manera

log x = Int 1 / x dx = sum x = 0 al infinito 1 / x = 1/1 + 1/2 + 1/3 + … a infi (Es una progresión armónica)

Ahora suma parcial s1, s2, s3 …

s1 = 1

s2 = 1 + 1/2 = 1.5

s3 = 1.5 + 1/3 = 1.83

s4 = 1.83 + 1/4 = 2.08

s5 = 2.08+ 1/5 = 2.28

s6 = 2.28 + 1/6 = 2.94

s7 = 2.94 + 1/7 = 3.08

s8 = 3.08+ 1/8 = 3.225

s9 = 3.22+ 1/9 = 3.386

… ..

Tenga en cuenta que es un crecimiento lento en el sentido de que la diferencia en los términos disminuye gradualmente. y toca la línea 4 en el infinito lo que llamas asintótico.

También tenga en cuenta que el crecimiento anterior está en la base de registro e.

Podemos cambiar la base también de la siguiente manera:

log (base a, digamos) x = ln x. log (base a) e

= log (base a) e (1 + 1/2 + 1/3 + 1/4 +… .. a infi)

Entonces s1, s2, s3, … el valor cambia por multiplicación por log (base a) e. Cuanto mayor sea el valor de a menor será el valor de log (base a) e y mayor será la diferencia entre los términos de 1 + 1/2 + 1/3 + 1/4 … toros.

Answer 2

Crecimiento lineal 1 2 3 4 5 6 7 8 9 10

Crecimiento cuadrático 1 4 9 16 25 36 49 64 81100

Crecimiento exponencial 1 2 4 8 16 32 64 128 256 512 1024

Crecimiento logarítmico (para claridad redondeada hacia abajo para omitir fracciones) 0 1 2 2 4 4 4 4 8 8 8 8 8 8 8 8

La intuición para el crecimiento logarítmico es, por ejemplo, la de la búsqueda binaria: “dado un intervalo de longitud n, ¿cuántas veces necesito dividirlo por 2 * hasta que termine con un solo número en el intervalo”.

[* o por 3 o 10 o 100, el logaritmo se puede tomar con cualquier “base”, en mi ejemplo 2, pero el crecimiento – con respecto a la notación O – es el mismo sin importar el que elija, por lo que es fácil pensar solo en 2 ]

Answer 3

Gracias por A2A.

• La progresión lineal se realiza con una diferencia común de d .
• La progresión exponencial se realiza con una relación común de r.
• La progresión logarítmica se realiza con una diferencia común de [matemáticas] log_bN – log_b (N-1) = log_b \ tfrac {N} {N-1} [/ matemáticas]

El crecimiento logarítmico es el inverso del crecimiento exponencial y es muy lento. Un ejemplo familiar de crecimiento logarítmico es el número de dígitos necesarios para representar un número, N, en notación posicional, que crece como [math] log_bN [/ math], donde b es la base del sistema numérico utilizado, por ejemplo, 10 para decimal aritmética.