Big-Oh наложит упорядоченный раздел на набор «обычных» функций?

Question

Пример в Этот ответ доказывает факт, знакомый CS студенты CS - что «Big-O» не общий порядок. Однако в большинстве случаев работы алгоритма проанализированы с использованием нотации Big-Oh, не экспрессируются в кусочно-форме, как этот пример. На самом деле, большинство алгоритмов я знаком с временем работы, выраженные с точки зрения полиномов, экспоненции и журналов.

Рассмотрим рекурсивно определенный класс функций, которые включают в себя $ f (n)= c $ для любой постоянной $ C $ , $ f (n)= n $ , и любые функции формы $ f + g, f \ cdot g, \ log (f), \ exp (f) $ где $ f, g $ находятся в классе. Делает $ o $ Заказанный раздел на этот класс функций? Функции с одним и тем же большим- $ o $ o $ o $ рост входит в той же части.

Вот мои мысли:

Обратите внимание, что указание $ f \ cdot g $ на самом деле избыточно, поскольку $ f \ cdot g=exp ( \ log (f) + \ log (g)) $ . Поскольку функции определяются индуктивно, возможно, существует индуктивное доказательство.

Answer 1

Это было показано hardy в своей монографии Заказы на бесконечность .