6/100 Dias Estudando Estruturas de Dados - Complexidades | As 3 Marias
Um pouco sobre Complexidades
O principal motivo para se usar estrutura de dados, é resolver problemas de forma eficaz e eficiente. Mas como sei se meu programa é eficiente? Ai que entra(lá ele) as complexidades.
-
Complexidade de Tempo
A
complexidade de tempoé usada para medir a quantidade de tempo necessária para executar o código. -
Complexidade de Espaço
A
complexidade de espaçosignifica a quantidade de espaço necessária para executar as funcionalidades do código.
"ahh, mas o tempo necessário para execução de um programa depende de vários fatores"
Para isso temos as notações assintóticas.
a notação assintótica é uma ferramenta matemática que calcula o tempo necessário em termos de tamanho de entrada e não requer a execução do código.
3 Marias
As três notações assintóticas a seguir são usadas para representar a complexidade de tempo dos algoritmos:
- Notação Big-O (O): Descreve o pior cenário.
- Notação OMega (Ω): Descreve o melhor cenário.
- Notação Theta (θ): Representa a complexidade média de um algortimo.
Matemática não é importante né? rsrs
Notação Big O
Sem dúvidas a notação mais utilizada na análise de um código é a Big-O. Ela fornece um limite superior do tempo de execução do código(ou a quantidade de memória usada em termos de tamanho de entrada).
Para um problema de tamanho N:
- Uma função de tempo constante é
Ordem 1:O(1)// + eficiente - Uma função de tempo linear é
Ordem N:O(N)// +/- eficiente(depende do tamanho de N) - Uma função de tempo quadrático é
Ordem N ao quadrado:O(N * N)// - eficiente
Notação OMega (Ω)
Em termos simples, Ω fornece um limite inferior para o desempenho de um algoritmo, indicando o menor tempo que um algoritmo pode levar para resolver o problema.
-
Cota Inferior Assintótica: Ω fornece um limite inferior assintótico, o que significa que estamos considerando o comportamento da função para tamanhos de entrada suficientemente grandes.
-
Relação com O (Big O): Enquanto a notação O descreve um limite superior, Ω descreve um limite inferior. Em alguns casos, podemos usar ambas as notações (Ω para inferior e O para superior) para obter uma descrição mais precisa do comportamento assintótico de um algoritmo.
A outra Maria é tímida...
Extras
Mais sobre Big(O): https://www.freecodecamp.org/portuguese/news/o-que-e-a-notacao-big-o-complexidade-de-tempo-e-de-espaco/
Mais sobre OMega (Ω): https://blog.pantuza.com/artigos/a-notacao-omega
Não é tão simples assim, mesmo o que foi colocado aqui, mas nem eu sei tanto para tentar corrigr corretamente. Eu só queria alertar para quem estiver lendo e dizer que o básico que importa mais é isso mesmo, só não é toda a verdade. Uma pessoa mais acadêmcia vai cuspir no texto :D Mas não somos acadêmicos.
Ajudei? Era o meu desejo.
Farei algo que muitos pedem para aprender a programar corretamente, gratuitamente. Para saber quando, me segue nas suas plataformas preferidas. Quase não as uso, não terá infindas notificações (links aqui).