algorithm - resueltos - Base de logaritmos en algoritmos de complejidad de tiempo.
conteo de instrucciones algoritmos (5)
En Ciencias de la Computación, a menudo es base 2. Esto se debe a que muchos algoritmos de dividir y conquistar que muestran este tipo de complejidad dividen el problema en dos en cada paso.
La búsqueda binaria es un ejemplo clásico. En cada paso, dividimos la matriz en dos y solo buscamos recursivamente en una de las mitades, hasta que llegue al caso base de un subarreglo de un elemento (o cero elementos). Al dividir una matriz de longitud n en dos, el número total de divisiones antes de alcanzar una matriz de un elemento es log2(n) .
Esto a menudo se simplifica porque los logaritmos de diferentes bases son efectivamente equivalentes cuando se analiza el análisis de algoritmos.
¿Cuál es la base del logaritmo en todos los algoritmos de complejidad de tiempo? ¿Es la base 10 o la base e?
Cuando decimos que la complejidad de ordenación promedio es O (n log n). ¿Es la base de log n 10 o e?
En el análisis de complejidad de Big-O, en realidad no importa cuál sea la base logarítmica. (Son asintóticamente iguales, es decir, difieren solo en un factor constante):
O(log2 N) = O(log10 N) = O(loge N)
La mayoría de las veces, cuando los matemáticos hablan de registros, tienen la intención implícita de basar e . Los científicos informáticos tienden a favorecer la base 2, pero en realidad no importa.
En términos de Big-O, la base no importa porque el cambio de la fórmula base implica que es solo una diferencia de factor constante.
Sin embargo, a veces es útil contar aproximadamente cuántas operaciones realiza un algoritmo. En este caso, la mayoría de las veces es base 2 debido a la naturaleza de la mayoría de los algoritmos de dividir y conquistar.
Hay alguna explicación en este sitio.
Básicamente, los logaritmos de la base 10 o base 2 o base e pueden intercambiarse (transformarse) a cualquier otra base con la adición de una constante. Por lo tanto, no importa la base para el registro.
La clave a tener en cuenta es que log2N crece lentamente. Duplicar N tiene un efecto relativamente pequeño. Las curvas logarítmicas se aplanan bien. source
Varía dependiendo del problema y en su mayor parte es irrelevante. Sin embargo, en muchos casos es base 2, por ejemplo, la búsqueda binaria es log (base 2) n. Puedes leer sobre esto en más detalle here .