Erhöht Big-OH eine bestellte Partition auf dem Satz der "üblichen" Funktionen?

Question

Das Beispiel in Diese Antwort beweist die Tatsache, dass CS-Studenten bekannt ist - dass das "Big-o" ist keine Gesamtbestellung. Die meisten Algorithmuslaufzeiten, die mit Big-OH-Notation analysiert werden, werden jedoch nicht in stückweise Form wie diesem Beispiel ausgedrückt. In der Tat bin ich mit den meisten Algorithmen eine Laufzeit vertraut, die in Bezug auf Polynome, Exponentiationen und Protokolle ausgedrückt wird.

Betrachten Sie die rekursiv definierte Klasse von Funktionen, die $ F (N)= C $ für jede konstante $ C $ enthalten , $ f (n)= n $ , und beliebige Funktionen des Formulars $ F + G, F \ cdot g, \ log (f), \ exp (f) $ Wobei $ f, g $ in der Klasse sind. Erhöht $ o $ eine bestellte Partition auf dieser Funktionsklasse auferlegen? Die Funktionen mit demselben Big- $ o $ Wachstum ist im selben Teil.

Hier sind meine Gedanken:

Beachten Sie, dass die Angabe von $ f \ cdot g $ tatsächlich redundant ist, da $ f \ cdot g=exp ( \ \ log (f) + \ log (g)) $ . Da die Funktionen induktiv definiert sind, gibt es vielleicht ein induktiver Beweis.

Answer 1

Dies wurde von Hardy in seiner Monographie gezeigt Bestellungen der Infinity .