Dúvida sobre progressão dos estudos em Java.

Eu estava começando a estudar complexidade de algoritmos quando um desenvolvedor Junior (sou estagiário) me disse "cara, se tu já estudou algoritmos, então não precisa disso, continua a estudar Banco de dados relacionais Java, pois esse assunto é bom de estudar posteiormente". Como já ficou explícito, já estudei os fundamentos de Java, Estrutura de Controle, Classes e Métodos, Arrays e Collections, POO, Lambdas e Stream API. O tópico posterior do curso a ser estudado é Banco de Dados Relacional, pois isso ele tinha dito isso.

Por que comecei a estudar a complexidade de algoritmos? Estava procurando uns exercícios de algoritmos em Java para aprimorar a minha lógica e velocidade na hora de resolver problemas, mas tais exercícios vinham pedindo um nível de complexidade determinado pela notação Big(O), e por tal motivo comecei a estudar o assunto, para que eu pudesse resolver os exercícios de acordo com o nível de dificuldade requisitado.

A questão é: ter conhecimento de complexidade de algoritmos, bem como saber analisar, é realmente necessário? Acredito que já sei a resposta (ahhhh desculpa se é uma pergunta besta, mas sou besta, fazer oq).

kht há 2 anos

Complexidade de algoritmos é uma daquelas coisas que vc só percebe que faz diferença quando vc conhece. Quem não conhece não vai perceber, na verdade sequer vai chegar a conceber que aquilo pode fazer alguma diferença. Exagerando um pouco, é como se o Tarzan dissesse que pode ir de cipó pra qualquer lugar e isso é o suficiente, pois ele não conhece nenhum outro meio de transporte, e portanto não consegue nem imaginar que há como ir mais rápido.

E o pior de tudo é que, de fato, na maioria dos casos comuns vai "funcionar". Afinal, para poucos dados, tudo é rápido. Hoje os computadores estão tão rápidos, que se um algoritmo tiver que manipular apenas 10, 500 ou 2000 itens, qualquer algoritmo vai ser "rápido".

No artigo indicado acima tem um exemplo claro desse problema. A tabela que tem lá é mais completa, mas enfim, vamos considerar apenas um algoritmo que tem complexidade O(n2) e outro que tem O(nlogn). Veja como a diferença fica cada vez maior conforme o tamanho dos dados aumenta:

n	nlogn	n2
1	0	1
16	64	256
256	2.048	65.536
4.096	49.152	16.777.216
65.536	1.048.565	4.294.967.296
1.048.476	20.969.520	1,09 trilhões
16.775.616	402.614.784	281,4 trilhões

Ou seja, conforme o N aumenta, o algoritmo O(nlogn) cresce a uma taxa muito menor do que o O(n2). E quanto maior o N, maior a diferença entre os dois.

O problema é que na maioria dos casos mais comuns, lidamos com poucos dados. Páginas e retornos de API web costumam ser paginados, raramente estamos lidando com centenas de milhões de itens. Por isso que na maioria dos casos "funciona" e as pessoas acham que não precisam saber sobre complexidade de algoritmos.

Para poucos itens, qualquer algoritmo rodará em menos de 1 segundo, o que é imperceptível para nós humanos. Mesmo que o algoritmo mais lento demore 0.1 segundo e o mais rápido demore 0.001 segundo (ou seja, 100 vezes mais rápido), ainda sim não perceberíamos a diferença. Só quando tivermos milhões de itens, e o algoritmo mais rápido rodar em 1 minuto enquanto o mais lento demora várias horas, é que as pessoas param para pensar no que estão fazendo.

Outro detalhe é que a complexidade de algoritmos está diretamente ligada a outro assunto importantíssimo: estruturas de dados.

Cada estrutura (fila, pilha, lista ligada, árvore, etc) tem a complexidade de suas operações muito bem documentadas. Por exemplo, "para adicionar elementos é O(n), para buscar um elemento é O(logn), para remover é O(n), etc". E a escolha da estrutura correta pode fazer toda a diferença no algoritmo: o seu caso vai ter mais alterações (adicionar/remover) ou acessos? Os dados precisam estar ordenados ou tanto faz em qual posição adicionar? etc etc etc... Sabendo das necessidades específicas, você consegue escolher a estrutura mais adequada, e essa simples escolha pode fazer toda a diferença no resultado final.

Mas tem gente que não liga pra isso e usa array (ou "objeto") pra tudo (e "funciona", pois sempre tem menos que 100 itens, então tanto faz). Por isso tem tanta gente que diz que não precisa saber, que nunca usou, etc. Só lamento...

musashifraco há 2 anos

Obrigado por esclarecer a questão, amigo. A tabela deixou bem claro a grandissíma diferença que existe. Esse conhecimento, aparentemente, é uma ponte para quem atravessa todos os dias o laguinho a pé. Parece fácil fazer a travessia, mas depois de um tempo se percebe o quão mais prático e e útil foi ter construído uma ponte enquanto outros se dedicaram apenas a se molhar no laguinho.

kht há 2 anos

Só pra ilustrar, um exemplo prático em JavaScript. Suponha que eu tenha um array assim: ```javascript [ { nome: 'Fulano', idade: 20 }, { nome: 'Ciclano', idade: 31 }, { nome: 'Beltrano', idade: 20 }, { nome: 'Trajano', idade: 31 }, { nome: 'João', idade: 42 }, ] ``` E eu queira criar outro array que tem os nomes agrupados por idade: ```javascript [ { idade: 20, nomes: [ 'Fulano', 'Beltrano' ] }, { idade: 31, nomes: [ 'Ciclano', 'Trajano' ] }, { idade: 42, nomes: [ 'João' ] } ] ``` A ideia mais simples é usar um `for`, e para cada elemento, verifico se a idade já existe no resultado. Se não existir, cria o array de nomes, e se já existir, adiciona nesse array: ```javascript // usando for e find const result = []; for (const item of dados) { // procura pela idade no resultado let elemento = result.find(e => e.idade == item.idade); if (!elemento) { // se não tem, cria o array elemento = { idade: item.idade, nomes: [] }; result.push(elemento); } // adiciona o nome elemento.nomes.push(item.nome); } console.log(result); ``` Ok, funciona. Mas esse algoritmo tem um porém: para cada item do array `dados`, eu uso `find` para verificar se a idade já está no resultado - pois eu tenho que saber se preciso adicionar uma idade que ainda não está lá. Só que a busca em um array é linear, ou seja, `find` no fundo é outro *loop* (que está "escondido", pois ele faz isso internamente). Claro que ele interrompe o *loop* quando encontra o elemento, mas mesmo assim, conforme o array `result` cresce, fica cada vez mais custoso percorrê-lo para fazer esta busca. Daria para melhorar isso usando inicialmente um objeto para mapear cada idade para seu respectivo array, assim o custo da busca é diminuído: ```javascript let result = {}; for (const item of dados) { result[item.idade] ||= { idade: item.idade, nomes: [] }; result[item.idade].nomes.push(item.nome); } result = Object.values(result); console.log(result); ``` O operador `||=` é usado para atribuir um valor caso ele ainda não esteja definido. Por exemplo, `a ||= b` é o mesmo que `a = a || b` (se `a` estiver definido, usa o valor dele, senão usa o valor de `b`). No caso, `result[item.idade]` estará definido somente se a idade já estiver no resultado. Caso não esteja, adiciona-a no objeto, cujo valor será o objeto que contém a idade e o respectivo array de nomes. Isso é mais rápido que `find` porque a busca de uma propriedade em objetos é mais rápida (não é linear como no array, não precisa fazer um *loop* pelos elementos até encontrar a idade). No final, pegamos apenas os valores do objeto, e o resultado é o array que queríamos. Fiz um teste usando o [Benchmark.js](https://benchmarkjs.com/), segue todo o código abaixo: ```javascript var Benchmark = require('benchmark'); var suite = new Benchmark.Suite; const dados = []; // cria 10 mil itens for (let i = 0; i < 10000; i++) { dados.push({ nome: 'Fulano ' + i, idade: i % 80 }); } suite .add('for/find', function () { const result = []; for (const item of dados) { let elemento = result.find(e => e.idade == item.idade); if (!elemento) { elemento = { idade: item.idade, nomes: [] }; result.push(elemento); } elemento.nomes.push(item.nome); } }) .add('object', function () { let result = {}; for (const item of dados) { result[item.idade] ||= { idade: item.idade, nomes: [] }; result[item.idade].nomes.push(item.nome); } result = Object.values(result); }) .on('complete', function () { console.log('Fastest is ' + this.filter('fastest').map('name')); }) .on('cycle', function (event) { console.log(String(event.target)); }) .run({ 'async': true }); ``` Criei um array com 10 mil itens, com idades variando entre 0 e 79. O resultado está abaixo (**lembrando que os números são de operações por segundo, ou seja, quanto mais, melhor**): ```none for/find x 1,021 ops/sec ±0.72% (90 runs sampled) object x 9,144 ops/sec ±1.70% (91 runs sampled) Fastest is object ``` Vale lembrar também que os números podem variar de acordo com cada máquina. Mas em geral, o resultado final (qual é mais rápido) não deve variar. Enfim, usando o objeto deu umas 9 mil operações por segundo, enquanto o `for` com `find` deu apenas mil. Se aumentarmos o intervalo de idades para 0 a 99, a diferença entre eles aumenta: ```none for/find x 849 ops/sec ±0.73% (88 runs sampled) object x 8,354 ops/sec ±1.03% (90 runs sampled) Fastest is object ``` Se usarmos um intervalo de 0 a 999 (sei que 999 é muito para idade, mas imagine que fosse outro campo, como uma pontuação qualquer, por exemplo), a diferença aumenta ainda mais: ```none for/find x 95.69 ops/sec ±2.09% (68 runs sampled) object x 6,275 ops/sec ±1.38% (79 runs sampled) Fastest is object ``` Sim, mais de 6 mil operações por segundo, contra menos de 100 (os números estão no formato americano, a vírgula separa os milhares e o ponto é o separador decimal). Quanto menos idades repetidas, pior fica, porque o array `result` fica com mais elementos, e `find` acaba - na média - demorando mais para verificar se uma idade já existe. Já para um objeto o impacto é menor, porque a busca por uma propriedade não é linear (provavelmente usa alguma tabela de hash ou algo similar - cuja busca é geralmente constante - para ser tão rápido). --- Mas como eu já disse, para arrays pequenos não faz tanta diferença assim, e em alguns casos o `for` pode até ser mais rápido. Por exemplo, para um array com 30 itens e idades entre 0 e 29, o `for` foi mais rápido: ```none for/find x 879,554 ops/sec ±1.50% (86 runs sampled) object x 774,850 ops/sec ±2.04% (82 runs sampled) Fastest is for/find ``` Isso porque tem o custo extra de criar o objeto e no final criar outro array contendo somente os valores (quando chamamos `Object.values`). Esse custo só se paga se tivermos mais elementos. E novamente, isso pode variar de acordo com o hardware, mas enfim, na minha máquina o `for` já ficou mais lento com apenas 50 itens. E reforço a questão de que isso será imperceptível para poucos arrays pequenos (a questão de 0.1 segundo versus 0.001 segundo, ambos não dá para perceber, apesar de um ter sido 100 vezes mais rápido). Isso só começa a fazer uma diferença notável com muitos arrays grandes, e por isso que muita gente não liga pra isso e acha que é inútil. Mas é importante saber sim. São várias dessas pequenas ineficiências que quando somadas acabam degradando aos poucos o sistema. Claro que se for um sistema simples e pequeno, de criticidade baixa, e que seguramente trabalha sempre com poucos dados, aí talvez não precise otimizar tanto. Mas é importante saber desses detalhes sim, para não ser pego de surpresa quando os problemas de desempenho começarem.

samuelhaidu há 2 anos

Excelente explicacação!! So queria fazer uma correção, hash table não tem tempo O(LogN) e sim O(1) ou seja é constante. E sim o javascript usa hash table no `object` e no `Map`. Quando você passa uma chave para um objeto ele transforma isso no hash que vai apontar diretamente para o enredeço de memoria (simplificando). Ou seja independente no numero de elementos dentro do `object` voce vai ter sempre o mesmo tempo de acesso.

kht há 2 anos

Já corrigi o texto, obrigado! Mas vale lembrar que "constante" não quer dizer "sempre o mesmo tempo", pois depende de detalhes internos do algoritmo. Por exemplo, conforme a quantidade de itens cresce, pode ter alguma demora adicional [para resolver colisões](https://en.wikipedia.org/wiki/Hash_table#Collision_resolution) (e o tempo total disso tudo depende dos algoritmos escolhidos), etc. Mas enfim, O(logn) estava errado mesmo, eu pensei uma coisa e escrevi outra :-)

maniero há 2 anos

Foge dessa pessoa! Sim, pode mostrar isso para ela. Se ela for só ingênua ela vai parar para pensar e revisar sua vida profissional. Mas minha experiência mostra que é comum casos assim não ser só ingenuidade, aí não tem o que fazer, siga a primeira recomendação, tem atitudes que são deletérias. Faça com todo mundo que diga para você aprender menos.

Você tem que estudar toda computação. Bem, quase toda, pelo menos toda a base da computação. Existem algumas coisas que se usam só em alguns casos. Vou contar uma anedota.

Eu fui palestrar em um evento chamado por uma pessoa que é referência para muita gente. Eu falei da complexidade de algoritmo. No fim a turma foi em algum bar e conversando lá ele me disse que em 15 trabalhando na área nunca usou isso. Eu disse que em 35 anos (na época) eu tinha usado todos os dias.

Você acha que o errado é ele que não usou ou eu que uso sem precisar? A pessoa não percebe algo errado se está "funcionando".

Fiat 147 todo detonado andando pelas ruas

Ele precisa fazer umas paradas de microsserviço porque senão o que ele faz não escala. Ele precisa fazer algo complexo para resolver o problema da baixa eficiência do que ele faz. Eu prefiro fazer o eficiente.

Uma vez me disseram que preferem fazer microsserviços porque eles não têm os melhores profissionais para dar eficiência. Mas microsserviços é distribuição, que é o problema mais difícil de fazer certo na computação, e por isso você vê cada vez mais aplicações/sites com dificuldades, vão funcionando aos trancos e barrancos. Complexidade de algoritmo é fundamento. Sem isso você não sabe programar, você engana. Está cada vez mais fácil enganar.

Já estudou os fundamentos da computação? Isso é o que importa. Já aprendeu como o Java funciona para aproveitar bem? Sabe usar a documentação como ninguém? Estão tinindo para resolver problemas, independente da codificação? Sabe estruturar seus dados de forma que atenda melhor às demandas? É nisso tudo que as pessoas pecam e tem a sua evolução comprometida.

A linguagem depois do bem básico você vai aprendendo sob demanda.

Orientação a objeto é um caso à parte. Isso é bem mais complicado do que ensinam e não é fácil achar como aprendi certo. Eu aprendi errado diversas vezes e agora nem sei se já cheguei no certo. Incrível como pessoas bem menos experientes acham que aprenderam certo. E eu vejo publicamente erros grotescos. Mas o importante é funcionar...

É claro que você não precisa ter o conhecimento acadêmico apurado, mas você entender o'que está fazendo pode te poupar muito problema.

Eu me destaquei na vida profissional só por um motivo, eu sei complexidade de algoritmo. Meus grandes feitos, e que alguns classificam como geniais, tamanho o ganho, e que eu sei que foi só eu saber os fundamentos, é bem simples e básico, não tem nada de inteligente no que eu faço, as pessoas se deslumbram porque como elas não entendem aquilo, parece mágica.

Desde a faculdade o que fiz foi o sistema do TCC que levava 3 meses para processar algo virar 20 minutos. O bill of materials que só podia ter 5 níveis de explosão para não ficar dias processando permitiu dezenas e resolver em minutos, ou o caso de qualquer relatório que demorava 30 minutos ou mais para emitir e fiz cair para menos de 30 segundos, alguns quase instantâneos, e fazer toda infra ficar folgada, de brinde. Poderia fazer uma lista enorme.

É por saber dessas coisas que o Stack Overflow, um dos 50 sites mais acessados do mundo (dependendo da época que verifique), pode rodar em 1 servidor, enquanto outros precisam de centenas ou milhares para carga semelhante. E não custa mais caro desenvolver isso, porque quando a pessoa sabe, é só aplicar, não é questão de fazer mais trabalho. Complexo, caro, ineficiente e com qualidade questionável é fazer microsserviços porque não está dando conta da carga de algo muito menor. Ou fazer cache porque tem algo muito ruim por trás (cahce é uma das cosias mais difíceis de administrar, vira e mexe vemos exemplos assim, já vi aqui mesmo).

Isso é parecido com dizer que não precisa de matemática para programação. Programação é matemática. Quando a pessoa diz isso ela não tem noção do que está fazendo.

Busque seu desenvolvimento em tudo, o tempo todo. Não se limite, tenha uma atitude de melhoria contínua, nenhum conhecimento é desperdício. Nunca trabalhei com química, mas de alguma forma foi útil eu ter feito práticas de laboratório na escola. O mesmo para fotografia que me ajudou a ser melhor programador, de formas não convencionais.

Se ajude a pensar cada vez mais. Tenha maneiras de ver problemas sob outras óticas. Sabe a coisa de aprender uma linguagem por ano? É para isso, não é para ter mais chances no mercado de trabalho, é ver como resolver o problema de forma diferente, e melhor. Tudo é questão de atitude, do que escolhe para te acompanhar.

Faz sentido?

Espero ter ajudado.

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

musashifraco há 2 anos

Obrigado por se dignar a responder. Acho que não foi a intenção dele me enganar, acredito ter sido só desconhecimento, pois o mesmo comprou 3 cursos incríveis e me deu de graça. Acho que aprender a analisar um problema e aprender a resolver um problema da melhor forma possível jamais será algo descatável; é conhecimento de base. "Desde a faculdade o que fiz foi o sistema que levava 3 meses para processar algo virar 20 minutos. O bill of materials que só podia ter 5 níveis de explosão para não ficar dias processando permite dezenas e resolver em minutos, ou qualquer relatório que demorava 30 minutos ou mais para emitir e caírem para menos de 30 segundos, alguns quase instantâneos, e fazer toda infra ficar folgada, de brinde. Poderia fazer uma lista enorme." - Isso é realmente incrível, espero um dia ser assim ks. Sobre a matemática, de fato as pessoas a ignoram, assim como a filosofia e outras áreas da ciência que ajudam a pensar de forma lógica (muito necessário para o TI) ou fora da caixa. "Faz sentido? Espero ter ajudado" - Faz sentindo sim, ajudou. Dei fork e uma star no repository. Agradeço-te!