Big-Oh impõe uma partição ordenada no conjunto das funções "usuais"?
-
29-09-2020 - |
Pergunta
O exemplo em Esta resposta prova o fato familiar para os alunos do CS - que o "Big-O" é não é um pedido total. No entanto, a maioria dos tempos de execução de algoritmo analisada usando a notação Big-Oh não são expressas em forma por partes como este exemplo. Na verdade, a maioria dos algoritmos que estou familiarizado com ter um tempo de execução expresso em termos de polinômios, exponenciações e logs.
Considere a classe de funções recursivamente definidas que inclui $ F (n)= C $ para qualquer constante $ c $ , $ f (n)= n $ e quaisquer funções do formulário $ f + g, f \ CDOT g, \ log (f), \ exp (f) $ onde $ f, g $ estão na classe. $ o $ Imponha uma partição ordenada nesta classe de funções? As funções com a mesma grande classe="recipiente de matemática"> $ o $ o crescimento é na mesma peça.
Aqui estão meus pensamentos:
Observe que especificar $ f \ cdot g $ é realmente redundante, já que $ f \ cdot g=exp ( \ log (f) + \ log (g)) $ . Como as funções são indutivamente definidas, talvez haja uma prova indutiva.
Solução
Isso foi mostrado por Hardy em sua monografia ordens de infinito .