Executando verificação de segurança...
15
rodriguesxxx
2 min de leitura ·

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ço significa 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.
representação das notações

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
representação da Big O

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.

representação da Omega

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

Fonte: https://github.com/rodriguesxxx/backend-developer/tree/main/Estrutura-de-dados-e-Algoritmos/Complexidades

Carregando publicação patrocinada...
1
maniero

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).

0