Complexidade de algoritmos: de O(1) a O(n) no real

O que o material de origem realmente diz

Por exemplo, complexidade de espaço Uma constante é basicamente a declaração de uma variável Quando você faz x igual a 1 aqui Isso daqui está guardando nessa referência da memória RAM O valor 1 Então poderia ser o valor 2 Poderia ser o valor 1 string Poderia ser uma string assim, teste Galera, passando rapidinho aqui para corrigir um erro que eu cometi Aqui quando a gente tem a complexidade de espaço constante O melhor exemplo é as constantes que a gente tem na programação.

Por que isso importa na operação

Dividido por 2, então aquele n é n dividido por 2, porque é metade e aqui a gente vai ter n dividido por 2 de novo, e por último n dividido por 2, então você percebe que a cada iteração ele está dividindo por 2, esse é um exemplo bem clássico de como funciona uma complexidade logarítmica eu não vou fazer em código aqui para não complicar mais e eu só trouxe esse exemplo para você Para você também ter uma ideia de como funciona a complexidade logarítmica.

Como estruturar o método

Porque quando a gente está fazendo essas junções, funções a gente fazendo o seguinte a gente passando por cada número do arrey vamos dizer que a gente tem um clone aqui então arrey2 é o arrey.clone só para ter os mesmos números aí a gente vai passar aqui pelo arrey2 por cada número também num 1 e num 2 Então explicando na prática, por que a complexidade aqui é quadrática?

Erros que drenam o resultado

A gente primeiro está rodando a complexidade de tempo, então esses array.its estão ocorrendo no processador, o .it, os dois, mas aqui na linha 27 a gente está puxando esses valores para dentro de um array. Então um exemplo de complexidade de espaço constante é literalmente uma constante na programação, que você pode atribuir algum valor, por exemplo, 10, Por exemplo, uma string Por exemplo, um float, por exemplo, um array.

Aplicação em uma semana

E a gente tem também a complexidade constante, ou seja, ela é apenas uma linha reta, porque não importa as variáveis, não importa o que você tenha, sempre vai ser esse tempo constante. Mas, já adiantando, basicamente, complexidade de espaço é a eficiência do seu algoritmo na memória RAM e a complexidade de tempo é a eficiência do seu algoritmo no processador, na CPU.

Sinais de que está funcionando

Bom, aqui eu deixei tanto a tela do meu VS Code quanto um gráfico da complexidade de BigO e esse gráfico mostra algumas complexidades que a gente tem. Na anotação do Big O, a gente pode chamar esse primeiro de n, e esse segundo é tamanho variável também, mas n já está sendo utilizado. Para cada elemento eu vou rodar n vezes e como a gente tem n elementos, a complexidade de tempo é n vezes n.

Próximo passo concreto

A complexidade de tempo, eu vou trazer um exemplo de código, que seria basicamente a gente percorrer por cada elemento do array. A gente tem a complexidade linear, que conforme você consegue ver aqui no gráfico, ela sobe de maneira constante. Então a complexidade de tempo para fazer essa operação por baixo dos panos no computador é uma complexidade constante.

Então quando a gente fala de complexidade de espaço também para array, isso daqui é o odn, certo? E isso é um bom exemplo da complexidade de espaço constante, porque essa constante não vai mudar. Então a gente tem uma complexidade aqui que anteriormente era N vezes N, agora é o quê? Primeira coisa, a gente tem aqui a complexidade quadrática, que é a pior que temos, ?

A gente tem a complexidade logarítmica, que é quando tem esse O log N. Ah, e tudo isso, galera, a gente está falando de complexidade de tempo, ? Então, a primeira coisa que a gente vai falar é a complexidade constante. A gente pode fazer esse mesmo exemplo para a complexidade de espaço também. Então, a complexidade logarítmica, eu vou fazer aqui de uma forma mais visual.

Meu nome é João, eu trabalho como engenheiro de software tem mais ou menos 5 anos, e desses 5 anos eu estou trabalhando para fora tem 3 anos, ou seja, eu moro aqui no Brasil e trabalho para uma empresa dos Estados Unidos. Então nós temos índices e aí o computador inteligentemente sabe, ah, ele está pedindo o índice Oi, eu vou lá nesse lugar e eu consigo pegar o valor dessa chave Oi.

Vocês concordam comigo que, basicamente, as combinações são 1, 1, 1, 2, 1, 3, 1, 4, e depois 2, 1, 2, 2, 2, 3, 2, 4, e por aí vai, certo? Quando a gente está acessando esse hash, então a gente pega aqui o hash na chave oi, Isso aqui tem acesso constante, então isso aqui é O de 1.

Então isso daqui pode ter 100, pode ter 1000, pode ter 2000, pode ter 3000, pode ter o número que for de elementos dentro desse array. Então, basicamente, um array dentro de outro, dessa forma assim, quando é o mesmo array, quando não são arrays diferentes, é n vezes n. Então, basicamente, eu estou com a linguagem, mas é mais para ser didática também, e para ilustrar para vocês como que funciona.

Porque à medida que eu for aumentando o meu array, a memória RAM precisa alocar mais espaço, então é uma forma linear. Não esqueça de engajar nesse vídeo, caso você tenha gostado ou o caso tenha sido útil para você de alguma forma.