Algoritmos – Notação Assintótica

A notação assintótica é um conjunto de ferramentas matemáticas utilizadas para descrever o comportamento de crescimento de funções.

---

A notação assintótica é um conjunto de ferramentas matemáticas utilizadas para descrever o comportamento de crescimento de funções, sendo fundamental na análise de algoritmos para definir limites de tempo de execução ou uso de memória à medida que o tamanho da entrada (n) aumenta.

1. Principais formas de notação:

1.1 Notação O (Limites Superiores)

A notação O é usada para definir um limite superior para uma função.

• Definição: Escrevemos que f(n) = O(g(n)) se existirem constantes positivas c e n₀​ tais que 0 ≤ f(n) ≤ cg(n) para todo n ≥ n₀
• Significado: Isso indica que a função f(n) não cresce mais rápido que g(n) (análogo a f(n) ≤ g(n) em termos de taxa de crescimento)
• Exemplo: 2n²=O(n³), pois para c=1 e n₀​=2, a condição é satisfeita

2. Notação Ω (Limites Inferiores)

Enquanto a notação O olha para cima, a notação Ω (ômega) define um limite inferior

• Definição: f(n)=Ω(g(n)) se existirem constantes c>0 e n₀​>0 tais que 0 ≤ cg(n) ≤ f(n) para todo n ≥ n₀​
• Significado: Indica que f(n) cresce pelo menos tão rápido quanto g(n) (análogo a f(n) ≥ g(n))

3. Notação Θ (Limites Justos/Firmes)

A notação Θ (theta) representa um limite assintoticamente firme, indicando que uma função está “presa” entre limites superior e inferior da mesma ordem de grandeza

• Definição: Ela é definida pela intersecção dos conjuntos O e Ω, ou seja, Θ(g(n))=O(g(n)) ∩ Ω(g(n))
• Significado: É análogo a dizer que f(n)=g(n) em termos de ordem de crescimento

4. Notações o e ω (Limites Estritos)

Essas notações são usadas para relações que não são “firmes”:

• Notação o (little o): Superior Estrito. Semelhante ao símbolo de “menor que” (<). Indica que f(n) cresce estritamente mais devagar que g(n)
• Notação ω (little ômega): Inferior Estrito. Semelhante ao símbolo de “maior que” (>). Indica que f(n) cresce estritamente mais rápido que g(n)

Considerações:

A notação assintótica refere-se a funções, não a valores isolados.

Embora seja comum usar o sinal de igualdade (ex: f(n)=O(n₂)), tecnicamente trata-se de uma definição de conjunto, onde a função pertence (∈) àquele conjunto de crescimento.

Essas notações permitem simplificar fórmulas complexas, focando apenas nos termos de maior ordem (ex: n²+O(n)=O(n²)).

---

Se tiver interesse em aprender Scrum, compre o Livro ou faça o curso Scrum Path+: Seu Caminho para a Agilidade através dos links abaixo:

---

---

Parceiros:

#Engenharia #Software #Algorítmo #Informática

---