¿Big-OH impone una partición ordenada en el conjunto de las funciones "habituales"?
-
29-09-2020 - |
Pregunta
El ejemplo en Esta respuesta demuestra que el hecho es familiar para los estudiantes de CS, que la "BIG-O" es No es un pedido total. Sin embargo, la mayoría de los tiempos de ejecución del algoritmo analizados utilizando la notación de BIG-OH no se expresan en forma a prueba de este ejemplo. De hecho, la mayoría de los algoritmos en la que estoy familiarizado con tener un tiempo de ejecución expresado en términos de polinomios, exponentes y registros.
Considerar la clase de funciones definidas recursivamente definidas que incluyen $ f (n)= C $ para cualquier constante $ C $ , $ f (n)= n $ , y cualquier función del formulario $ f + g, f \ CDOT G, \ log (f), \ exp (f) $ donde $ f, g $ están en la clase. ¿ $ o $ imponer una partición ordenada en esta clase de funciones? Las funciones con el mismo Big- $ o $ El crecimiento está en la misma parte.
Aquí están mis pensamientos:
Tenga en cuenta que especificar $ f \ cdot g $ es realmente redundante, desde $ f \ cdot g=exp ( \ log (f) + \ log (g)) $ . Dado que las funciones se define inductivamente, quizás haya una prueba inductiva.
Solución
Esto fue mostrado por Hardy en su monografía órdenes de infinito .