Descreva exemplos de crescimento não clássico.
Passo 1
Você perguntou: “Descreva exemplos de crescimento não clássico.”
Vou interpretar isso como pedir exemplos de funções (ou leis de crescimento) cujo comportamento para foge do padrão mais comum (por exemplo: simples polinomial ou simples exponencial) e também explicações didáticas de por que cada exemplo é considerado “não clássico” e como analisá-lo.
Informações que vou usar e entregar: uma definição clara de como comparamos crescimentos assintóticos, uma lista de exemplos variados de crescimento não clássico, e para cada exemplo uma explicação passo a passo de como entender/medir esse crescimento (com limites, comparação assintótica, e ferramentas como L’Hôpital e Stirling quando necessário).
Vou interpretar isso como pedir exemplos de funções (ou leis de crescimento) cujo comportamento para
Informações que vou usar e entregar: uma definição clara de como comparamos crescimentos assintóticos, uma lista de exemplos variados de crescimento não clássico, e para cada exemplo uma explicação passo a passo de como entender/medir esse crescimento (com limites, comparação assintótica, e ferramentas como L’Hôpital e Stirling quando necessário).
Passo 2
O que significa “comparar crescimentos”? Vou te ensinar a linguagem mínima que precisa para entender as comparações:
- Dizemos que
cresce menos que quando
Isso se escreve
. Aqui
e
são funções reais positivas para
grande.
- Dizemos que
e têm o mesmo crescimento assintótico quando
ou seja,
.
- A notação
significa que existe constante e tais que para . Isso é útil para comparações rápidas.
Esses conceitos são as “ferramentas” que vamos usar para dizer por que um exemplo é mais lento ou mais rápido que outro.
Passo 3
Rápido lembrete do “clássico” para termos ponto de referência (não resolvo nada, só marco a escala):
- Crescimentos muito lentos:
. - Crescimentos polinomiais:
com . - Crescimentos exponenciais:
com . - Crescimentos superexponenciais: iterações de exponencial
, etc.
“Não clássico” será qualquer exemplo que não caiba bem nessa hierarquia simples (por exemplo: mistura de fatores, oscilações, crescimento irregular, crescimento subexponencial mas maior que todo polinômio, etc.). Agora vamos aos exemplos concretos e à didática de cada um.
Passo 4
Exemplo 1 — Funções lentamente variáveis:
e
.
Por que são “não clássicas”? Porque crescem mais devagar que qualquer potência positiva de : para todo
,
Por que são “não clássicas”? Porque crescem mais devagar que qualquer potência positiva de
Como ver isso na prova (método): aplicar L’Hôpital à
. Veja:
Isto ensina: logaritmo é “muito menor” que qualquer polinômio;
é ainda mais lento.
Passo 5
Exemplo 2 — Funções polinomiais com fator log:
(com
).
Por que é interessante? Porque representam crescimento “próximo” ao polinomial mas ligeiramente maior. Comparações úteis:
Por que é interessante? Porque representam crescimento “próximo” ao polinomial mas ligeiramente maior. Comparações úteis:
- Se
então . Em prova: basta dividir e usar que . - Já
é para todo (ou seja, ainda menor que exponencial).
Essa família aparece muito em estimativas finas (por ex. em teoria de números ou análise assintótica).
Passo 6
Exemplo 3 — Subexponenciais:
,
com
.
Por que são “não clássicas”? Estão entre polinômios e exponenciais clássicas : crescem mais rápido que todo polinômio, mas mais devagar que
para qualquer
. Demonstração típica: para qualquer
,
Por que são “não clássicas”? Estão entre polinômios e exponenciais clássicas
pois o log do denominador cresce como
que domina
para
grande. E para qualquer
,
pois
. Em provas, usar o comparador no expoente é a forma direta: comparar os expoentes.
Passo 7
Exemplo 4 — Superexponenciais/iterações:
, ou em notação
.
Por que é “não clássico”? Porque cresce bem mais rápido que qualquer exponencial simples . Em provas, para comparar
e
, olhe para o quociente:
Por que é “não clássico”? Porque cresce bem mais rápido que qualquer exponencial simples
pois
domina linearmente
. Essas funções aparecem em problemas de complexidade extrema e em algumas séries singulares.
Passo 8
Exemplo 5 — Fatorial e
:
ou
para
contínuo.
Por que é especial? cresce mais rápido que
para qualquer
? Na verdade,
cresce mais rápido que
somente se compararmos a taxa por termos (mas
é superexponencial no sentido de
— Stirling). Ferramenta de prova (Stirling):
Por que é especial?
Isso te dá a ordem:
é exponencial em
, muito maior que
para base fixa
. Em provas envolvendo somatórios com
é comum aplicar essa aproximação.
Passo 9
Exemplo 6 — Oscilações multiplicativas:
ou
.
Por que é não clássico? Porque não é monotônico: a função alterna entre ordens diferentes. Por exemplo, toma valores entre
e
(pois
). Assim não existe um único “taxa” de crescimento — o comportamento depende de subsequências. Como analisar numa prova: mostre que existem subsequências
com
onde
, e outras com
onde
. Isso mostra que limites simples podem não existir e atenção ao falar de crescimento assintótico.
Por que é não clássico? Porque não é monotônico: a função alterna entre ordens diferentes. Por exemplo,
Passo 10
Exemplo 7 — Funções com crescimento irregular:
.
Por que é curioso? O fator oscilatório faz com que
oscile entre cerca de
e
multiplicativamente. Embora em escala geral o comportamento seja exponencial, localmente a função pode ficar próxima de zero (quando
). Em provas, isso mostra que ser "da ordem de
" não implica monotonicidade ou que todos os limites subsequenciais existam.
Por que é curioso? O fator oscilatório
Passo 11
Exemplo 8 — Funções regularmente e lentamente variáveis (conceito importante):
- Uma função
é lentamente variável se, para todo ,
Ex.:
,
.
- Uma função
é regularmente variável de índice se
com
lentamente variável. Ex.:
.
Por que serve? Esse conceito ordena muitos crescimentos “não clássicos” e é muito útil em provas de análise e probabilidade assintótica (caudas de distribuição, etc.). A técnica é fatorar o crescimento polinomial dominante e estudar o fator lento .
Por que serve? Esse conceito ordena muitos crescimentos “não clássicos” e é muito útil em provas de análise e probabilidade assintótica (caudas de distribuição, etc.). A técnica é fatorar o crescimento polinomial dominante e estudar o fator lento
Passo 12
Exemplo 9 — Crescimento estocástico/esperado: processos de ramificação ou crescimento aleatório.
Aqui “não clássico” significa que a taxa média pode ser exponencial, mas trajetórias individuais podem ter comportamento muito diferente (extinção, explosão em subamostras). Ferramenta: trabalhar com esperança e variância, e distinguir crescimento em média de crescimento quase certo. Embora este tópico seja mais de probabilidade, é um exemplo concreto de crescimento que não se encaixa em uma simples curva determinística.
Aqui “não clássico” significa que a taxa média pode ser exponencial, mas trajetórias individuais podem ter comportamento muito diferente (extinção, explosão em subamostras). Ferramenta: trabalhar com esperança
Passo 13
Resumo prático para aplicar na prova (como decidir que tipo é):
- Calcule
. Se for finito e positivo, é polinomial em ordem. Se esse limite é infinito, costuma ser superpolinomial. - Compare expoentes: olhar para o expoente em funções do tipo
. Se então é subexponencial frente a . - Procure fatores lentamente variáveis
(logs, log-logs) que alteram a ordem só levemente. - Verifique monotonicidade/oscilações: se há seno/cosseno dentro de expoentes ou potências, cuidado: pode não existir limite único.
Esses passos te ajudam a classificar rápido e escrever justificativas curtas e seguras na prova.
Resposta
funções regularmente variáveis
crescimentos estocásticos (ex.: processos de ramificação, onde trajetórias individuais podem divergir do crescimento médio)