Definição de para funções negativas

Estou trabalhando no livro didático CLRS Algorithms da 3ª edição e no capítulo 3 uma discussão começa sobre a notação assintótica que começa com a notação . Eu entendi a definição inicial de:$\Theta$

Mas então, na próxima página, o texto diz que:

A definição de exige que todo membro seja assintoticamente não-negativo, ou seja, que seja não-negativo sempre que for suficientemente grande. (Uma função assintoticamente positiva é positiva para todos os suficientemente grandes .) Consequentemente, a própria função g (n) deve ser assintoticamente não-negativa, ou então o conjunto está vazio.$\Theta(g(n))$$f(n) \in \Theta(g(n))$$f(n)$$n$$n$$\Theta(g(n))$

Na última parte, sobre como se a função é negativa, o conjunto está vazio e o requisito geral de uma função positiva é meio confuso. Alguém aí pode esclarecer essa definição para mim e o que isso significa, possível com um exemplo, seria muito apreciada.$\Theta(g(n))$

Isso é apenas um detalhe técnico. Na análise assintótica, estamos apenas "realmente" interessados ​​em funções positivas como ou . No entanto, se quisermos ser muito formais e gerais, poderemos levar em consideração funções não positivas (e isso pode torná-lo útil, veja abaixo). A definição de afirma que se, a partir de algum ponto, é delimitado de ambos os lados por constantes e, além disso, . (É isso que você obtém se desenrola a definição.) Em particular, se , então, a partir de algum ponto, é não negativo.$n^3$$n\log n$$\Theta$$f(n) = \Theta(g(n))$$f(n)/g(n)$$g(n) \geq 0$$f(n) = \Theta(g(n))$$g$

Aqui está uma definição alternativa de big . Suponha que são funções positivas , ou seja, . Então se existirem constantes positivas modo que . Não sei por que a definição mais complicada é apresentada nos textos introdutórios.$\Theta$$f,g \colon \mathbb{N} \rightarrow \mathbb{N}$$f(n),g(n)>0$$f(n) = \Theta(g(n))$$c_1,c_2$$c_1 \leq f(n)/g(n) \leq c_2$

Quais são as vantagens da definição mais complicada? Ele pode lidar com funções que possuem alguns valores não positivos (deve haver um número finito deles). Por exemplo, essa definição acomoda a instrução (true) . Embora as funções encontradas na prática sejam geralmente positivas, às vezes podem ser encontradas funções negativas: por exemplo, digamos que estamos interessados ​​em alguma função complicada genuína , e a estimamos a partir de baixo por uma função , que é negativa para pequeno .$n-10 = \Theta(2n-30\log n)$$k$$t$$n$

Por que pode estar vazio$\Theta(g)$

Segue diretamente da definição.

A parte importante aqui é esta:$f(n) | \exists\, c_1 > 0: 0 \leq c_1 g(n)$

Obviamente, a restrição em (a partir de agora, nem depende de ), afirma que multiplicado por alguma constante positiva deve ser positivo em si (para grandes valores de , implícitos daqui em diante ).$f$$f$$g$$c_1$$n$

Obviamente, se não for estritamente positivo, essa restrição impedirá que todas as funções possíveis sejam membros do conjunto .$g$$f$$\Theta(g)$

Daqui resulta que esse conjunto estará vazio.

Para todo , é estritamente positivo$f \in \Theta(g)$$f$

Isso também segue diretamente da mesma parte da definição:$f(n) | \dots : 0 \leq f(n)$

Obviamente, se não for estritamente positivo, a condição não será atendida; portanto, nenhum pode ser contido em .$f$$f$$\Theta(g)$

Nota : Não tenho muita certeza do que não está claro para você, porque tudo que você escreveu é "confuso".