8
Considerando O (log (N)) para la complejidad del tiempo, ¿cuál es la base del registro?¿Cuál es la base del logaritmo para los propósitos de Algoritmos?
A
Respuesta
15
Todos los logaritmos están relacionados por alguna constante. (De ahí el change-of-base formula). Como generalmente no tomamos en cuenta las constantes en el análisis de complejidad, la base no importa.
Por lo general, la base se considera que es 2, al derivar el algoritmo. Considere un tipo como merge sort. Puede construir un tree y el árbol tiene una altura de log₂ n, porque cada nodo tiene dos ramas.
+0
Me atrevería a enfrentar la segunda oración del primer párrafo ("la base no importa") para que sea una respuesta aún mejor. –
10
No importa, la complejidad relativa es la misma independientemente de la base utilizada.
+0
Hmmm. Si extiende lógicamente esta afirmación, estaría diciendo que O (n^2) tiene la misma complejidad relativa que O (n^3). –
+0
No, en absoluto. Gran diferencia entre 1 millón cuadrado o en cubos. Pero log2, log10, log100? No hay mucha diferencia en absoluto. – cletus
+0
@ Andrew Shepherd - Eso no es correcto. log_a (2n)/log_a (n) = log_b (2n)/log_b (n) para cualquier ayb – mob
1
Una manera de pensar de ello es que O (log X) = O (log X) = O (log N X)
Cuestiones relacionadas
- 1. Cálculo del logaritmo Base-n en Ruby
- 2. Algoritmo del logaritmo discreto
- 3. base de logaritmos en algoritmos de complejidad de tiempo
- 4. ¿Cuál es la diferencia entre los algoritmos genéticos y evolutivos?
- 5. ¿Cuál es la forma más rápida de repasar los algoritmos para una entrevista técnica (el lunes)?
- 6. Analizando algoritmos para la complejidad del tiempo
- 7. ¿Cuál es una buena fuente para algoritmos geométricos?
- 8. Función de logaritmo de una base entera arbitraria en C
- 9. ¿Cuál es el elemento HTML5 más adecuado para "limpiar: ambos"; ¿Propósitos?
- 10. algoritmos para evaluar las respuestas del usuario
- 11. Calcular logaritmo discreto
- 12. ¿Cuál es la "mejor" base de datos para incrustado?
- 13. ¿Cuál es la diferencia entre los algoritmos de "escalada" y "codiciosos"?
- 14. ¿Cuál es el estado actual de los algoritmos de compresión de solo texto?
- 15. #line - propósitos de?
- 16. ¿Cuál es el XPath correcto para "todos los nodos exactamente uno debajo del nodo base?"
- 17. OOP vs PP para los algoritmos
- 18. ¿Cuál es la sintaxis óptima del enlace html para usar para los iconos/faviones del sitio?
- 19. (Diseño de la base de datos - atributos de los productos): ¿Cuál es la mejor opción para el diseño de la base de datos de atributos del producto?
- 20. Logaritmo de entero rápido para el caso especial
- 21. ¿Cuáles son los propósitos de las clases internas
- 22. ¿Cuál es la "clase base" para los tipos de valores numéricos C#?
- 23. Código EF La primera columna adicional en la tabla de unión para los propósitos que ordenan
- 24. Logaritmo inexacto en Python
- 25. ¿Cómo funcionan los algoritmos de recomendación automatizados?
- 26. ¿Cuál es la ubicación predeterminada para los registros de MSBuild?
- 27. ¿Cuál es la mejor base de datos DLL-Base para .NET?
- 28. eligiendo entre los algoritmos
- 29. Algoritmos de personalización del perfil
- 30. Recursos para principiantes/introducciones a los algoritmos de clasificación
duplicado de: http: // stackoverflow. com/questions/1569702/is-big-ologn-log-base-e – outis