Big-OH是否对“通常”功能集中有序分区？

Question

此答案证明了CS学生熟悉的事实 - “BIG-O”是不是总订单。但是，使用大OH表示法分析的大多数运行时间不像本例一样以分段形式表示。实际上，我熟悉的大多数算法都有在多项式，指数和日志方面表达的运行时间。

考虑递归定义的函数类，其中包括 $ f（n）= c $ 对于任何常量 $ c $ ， $ f（n）= n $ ，以及表单 $ f + g，f的任何功能\ cdot g，\ log（f），\ exp（f）$ 其中 $ f，g $ 在类中。 $ o $ 在这类功能上强加一个有序的分区？具有相同大 - $ o $ 增长的函数在同一部分中。

这是我的想法：

注意，指定 $ f \ cdot g $ 实际冗余，因为 $ f \ cdot g=exp（ \ log（f）+ \ log（g））$ 。由于函数是局部定义的，可能存在电感证明。

Answer 1

这是由hardy在他的monograph 。