Startec

Startec

Estrutura de Dados #1 · meritissimo1

Mai 21, às 23:56

·

4 min de leitura

·

0 leituras

Já faz um tempo que não escrevo sobre esse assunto mas, antes tarde do que nunca 🤝 Continuando da onde eu parei (Estrutura de Dados #0) hoje eu quero falar sobre Complexidade de Algoritm...
Estrutura de Dados #1 · meritissimo1

Já faz um tempo que não escrevo sobre esse assunto mas, antes tarde do que nunca 🤝

Continuando da onde eu parei (Estrutura de Dados #0) hoje eu quero falar sobre Complexidade de Algoritmos e por que você deveria pensar duas vezes antes de colocar um While/for dentro do outro.

Já deixando um disclaimer, eu não sou nenhum professor universitário que entende 100% do assunto, sou só um estudante que gostou da matéria Estrutura de Dados :).

O estudo de Complexidade de Algoritmos envolve analisar o tempo de execução de determinado algoritmo e por isso, esse assunto também pode ser chamado de Tempo de Complexidade ou em English - Time Complexity. A importância de se estudar quanto tempo seu algoritmo levará pra ser executado numa determinada situação parece ser bastante auto explicativa, mas dando um exemplo, imagine que você é um(a) engenheiro(a) de software da Twitch e que agora você precise ordenar todos os canais online baseado no número de espectadores de cada canal. Dependendo da forma que você faça isso, talvez o seu algoritmo leve muito tempo para terminar a execução gastando muito recurso de processamento, e levando em consideração que estamos falando de uma grande empresa com muitos usuários e muitos dados, isso seria bem ruim. Nesse caso, você teria que antes mesmo de começar a escrever qualquer código, analisar como o algoritmo se comportaria no pior caso possível e essa analise é feita usando uma notação matemática (eu acho que exclusiva da computação) conhecida como Notação Big O, ou O Grande. A Notação Big O foca em analisar o comportamento do algoritmo no pior caso possível. Existem outras notações para melhor caso e caso médio, mas vamos ver aqui somente a Big O mesmo. Aqui são algumas exemplos:

  • O(1) -> As instruções são constantes, independente do n° de elementos.
  • O(n) -> No pior caso teremos n instruções e o crescimento é linear.
  • O(n²) -> No pior caso teremos n² instruções e o crescimento é exponencial.
  • O(log(n)) -> No pior caso teremos log2(n) = x, onde x é o n° de instruções e o crescimento é esse aqui da foto haha.

Big O Notation

A forma como eu aprendi complexidade foi analisando algoritmos e é o que nós vamos fazer agora!

Trouxe aqui 3 algoritmos de ordenação bem conhecidos: Insertion Sort, Selection Sort, Bubble Sort :)

Para entender a complexidade de um algoritmo, precisamos entender o que ele faz e principalmente COMO ele faz. Então começando pelo Insertion Sort, vamos escrever em poucas palavras o que ele faz e como, de uma forma que já nos de a resposta da complexidade

  • Insertion Sort: Para cada elemento, busca-se a posição correta no vetor. Ou seja, para cada N elementos temos que percorrer N posições, Logo, sua complexidade é O(n²).

Perceba que nós chegamos na complexidade sem escrever nenhuma linha de código! basta dizer da forma certa o que ele faz e como. Vamos tentar com os outros.

  • Selection Sort: Para cada posição, busca-se o elemento correto no vetor. Ou seja, Para cada N posições temos que percorrer N elementos, Logo, sua complexidade é O(n²).

e por fim,

  • Bubble Sort: Para cada par de elementos, busca-se a posição correta relativa no vetor. Ou seja, Para cada N pares de elementos temos que percorrer N posições, Logo, sua complexidade é O(n²).

Só com base nessas simples frase, qualquer pessoas que não seja um programador chaves haha, consegue implementar os algoritmos acima em QUALQUER LINGUAGEM! Inclusive, recomendo fortíssimo vocês implementarem esses algoritmos até pra entenderem o que eu falei lá no início, fica aí o desafio.

Exercitem essa dica de resumir o algoritmo em poucas palavras já deixando claro a complexidade e se quiserem, respondam aqui como fizeram 😁

Alguns materiais adicionais:
Insertion Sort 💃
Selection Sort 💃
Bubble Sort 💃


Continue lendo

DEV

Authentication system using Golang and Sveltekit - Dockerization and deployments
Introduction Having built out all the features of our application, preparing it for deployment is the next step so that everyone around the world will easily access it. We will deploy our apps (backend and...

Hoje, às 19:52

DEV

LEARN API AND ITS MOST POPULAR TYPE
An API (Application Programming Interface) is a set of rules and protocols that allows different software applications to communicate and interact with each other. It defines the methods, data structures, and...

Hoje, às 19:26

AI | Techcrunch

Investors take note: Wildfire smoke will spark a surge in East Coast climate tech startups
As smoke from Canadian wildfires has enveloped large swathes of the East Coast, millions of people have found themselves trapped inside, gazing out on orange skies and hazy cityscapes. The air quality index —...

Hoje, às 18:08

DEV

A Plain English Guide to Reverse-Engineering the Twitter Algorithm with LangChain, Activeloop, and DeepInfra
Imagine writing a piece of software that could understand, assist, and even generate code, similar to how a seasoned developer would. Well, that’s possible with LangChain. Leveraging advanced models such as...

Hoje, às 18:08

DEV

Finding Harmony in Marketing and UX
When we think of teamwork in the world of user experience (UX), we often imagine design and engineering working together. However, the idea of design and marketing working together is not as common. While...

Hoje, às 17:02

DEV

💡 Where to Find Inspiration for Building Your Next App
The first steps before turning your ideas into code. Whenever I’m trying to think of an idea to build a new application or website and I get stumped on what to do, there’s one phrase that always comes to...

Hoje, às 16:58

DEV

How to create 700+ SEO optimised pages for website in 1 h using Next.JS, OpenAI, Postgres
Small intro, I started learning coding couple of months before and since then experimenting with different small side projects. So this I show coding still looks for me:) What did I build this...

Hoje, às 16:37

DEV

Angular Project Mongodb database Connect | Angular Website Project | Angular App
Angular Project Mongodb database Connect | Angular Website Project | Angular App - YouTube ​ @softwaretechit Download Our App:- https://blog.softwaretechit.com/p/download.htmlWhat will we Learn In This...

Hoje, às 16:10

AI | Techcrunch

Meta warned it faces 'heavy sanctions' in EU if it fails to fix child protection issues on Instagram
The European Union has fired a blunt warning at Meta, saying it must quickly clean up its act on child protection or face the risk of “heavy sanctions”. The warning follows a report by the Wall Street...

Hoje, às 16:03

DEV

Taking Control with PostgreSQL Functions: Closing the Gap to ORM Functionality
Unveiling the Disparity: Understanding the Divide Between Direct Driver and ORM Functionality When it comes to choosing the technologies for developing a backend and manipulating data in a database like...

Hoje, às 16:02