¿Cuál es la base del logaritmo en todos los algoritmos de complejidad de tiempo? ¿Es base 10 o base e?base de logaritmos en algoritmos de complejidad de tiempo
Cuando decimos que la complejidad promedio de clasificación es O (n log n). Es la base de log n 10 o e?
En Informática, a menudo es la base 2. Esto se debe a que muchos algoritmos de división y conquista que presentan este tipo de complejidad están dividiendo 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 llegar a un caso base de una submatriz de un elemento (o cero elementos). Al dividir una matriz de longitud n en dos, el número total de divisiones antes de llegar a 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.
En el análisis de complejidad Big-O, en realidad no importa cuál es la base del logaritmo. (Son asintóticamente la misma, es decir, que difieren sólo en un factor constante):
O(log2 N) = O(log10 N) = O(loge N)
mayoría de las veces cuando los matemáticos hablan de registros, que implícitamente significa basar e. Los científicos informáticos tienden a favorecer a la base 2, pero en realidad no importa.
Bueno, siempre hay [notación suave-O] (http://en.wikipedia.org/wiki/Big_O_notation#Extensions_to_the_Bachmann.E2.80.93Landau_notations) para que ... – hugomg
Varía según el problema y en su mayor parte es irrelevante. Sin embargo, en muchos casos es la base 2, por ejemplo, la búsqueda binaria es log (base 2) n. Puede leer sobre esto con más detalle here.
En términos de Big-O, la base no importa porque el cambio de 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 la base 2 debido a la naturaleza de la mayoría de los algoritmos de división y conquista.
Hay alguna explicación en this site
Básicamente, los logaritmos de base 10 o de la base 2 o base e se pueden intercambiar (transformado) 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. Doblar N tiene un efecto relativamente pequeño. Las curvas logarítmicas se aplanan muy bien. source
Ups! Tienes razón, editado. – spacemanaki
En realidad, la base es importante en el análisis de complejidad. Depende de la función que estás analizando. Por ejemplo 'O (2^(log_2 (n))) = O (n)', mientras ''O (2^(ln (n))) = O (n^0.69 ...)', entonces estas complejidades son diferente. Pero eso se debe a que, en la función '2^logn', si cambia la base del logaritmo, cambia una" constante "que es un exponente de algo, y no una constante multiplicativa-aditiva. – Bakuriu
+1 para Bakuriu, la gente suele olvidar este caso. –