Isso foi engraçado! Comunicar-se com Big O é uma das primeiras transições de derreter o rosto para desenvolvedores em início de carreira. Vejamos o porquê. Mas primeiro, um pit stop. Você se lembra daqueles problemas de palavras absolutamente ridículos da escola primária? Sally foi ao supermercado e comprou 37 melancias. Ela tinha $ 20 dólares. Cada melancia custa US$ 0,70. Quanto dinheiro Sally tem quando chega em casa? Você ficou se perguntando: "Como diabos Sally vai chegar em casa? Com 37 melancias?! $ 6,00 não serão suficientes para conseguir um Uber com espaço suficiente para os melões ... o que Sally está fazendo ?!" Sally boba. Algumas pessoas dizem que isso é perder a floresta para as árvores. Eu digo que é apenas uma maneira terrivelmente preguiçosa de construir problemas práticos. O do é poder falar, literalmente com outras , sobre uma qualidade de nosso ofício. O foco particular aqui é permitir a comparação entre soluções à medida que o tamanho da entrada aumenta. objetivo Big O Notation se comunicar pessoas no pior cenário Queremos poder falar sobre soluções potenciais (o ) de forma abstrata. Este é um ponto crucial: . , , com os dados que . Quando brincamos com essas ideias, assumimos um conjunto de dados teoricamente gigantesco, mas finito. mesmo que dizer: algoritmos em abstrato Não nos importamos de forma alguma temos Quando pensamos nos dados que , isso é um raciocínio concreto. Quando pensamos na notação O grande, estamos raciocinando de forma abstrata. É FÁCIL cair no raciocínio concreto. É aqui que passamos a maior parte da vida. É fácil, geralmente óbvio e confortável. temos Devo atravessar a rua agora? Existe um carro? Não? Ok, cruze. Não faça isso ao raciocinar de forma abstrata! Definições, Rapidamente Você se importa se eu te fizer um favor aqui? Há um monte de termos matemáticos que também podem atrapalhar. Aqui está um visual, em ordem, do melhor para o pior caso, para alguns termos Big O comuns. Precisamos deles para que possamos pensar e aprender, em vez de ficarmos presos à terminologia. O(1) - "Tempo Constante" Não importa o tamanho da entrada, o sistema sempre retorna o resultado no mesmo período de tempo. O(log n) - "Log Time" À medida que a solução (ou algoritmo) itera sobre a entrada, cada iteração fica mais rápida! O(n) - "Tempo Linear" À medida que o algoritmo itera, cada iteração leva a mesma quantidade de tempo que a iteração anterior. O(n log n) - nenhuma terminologia sofisticada aqui Mostra que as ideias podem ser combinadas (caramba). À medida que iteramos, cada iteração fica mais lenta, mas fica mais lenta bem devagar. O(n^2) - "n ao quadrado" Para cada iteração, as iterações ficam mais lentas rapidamente. O(n!) - "n fatorial" Para cada iteração, as iterações ficam mais lentas super rápido. O objetivo é tentar ficar o mais longe possível de "n fatorial" e tentar não ficar muito pior que Constant. Com tudo isso entendido, vamos agora tentar preencher a lacuna. Fazendo a ponte entre o pensamento concreto e abstrato Entendendo a notação O grande A notação Big O é usada para descrever o desempenho ou a complexidade de um algoritmo (solução). Ele fornece uma compreensão de alto nível de como um algoritmo (solução) funcionará à medida que o tamanho da entrada aumenta. Por exemplo, um algoritmo com complexidade O(n) terá seu tempo de execução aumentado linearmente com o tamanho da entrada. Pensamento Concreto vs Abstrato O desafio surge quando os desenvolvedores confundem o raciocínio sobre dados específicos com o raciocínio sobre o próprio algoritmo. Frases como "mas esses dados são reais" podem sinalizar essa confusão. Embora raciocinar sobre os dados reais possa ajudá-lo a começar, é vital separar a solução da entrada atual. Por que o mal-entendido? Os desenvolvedores em início de carreira podem cometer esse erro devido à falta de experiência com problemas de escala maior ou por estarem muito absortos nas especificidades de um problema atual. É essencial separar os detalhes concretos da complexidade abstrata para criar soluções escaláveis. Consequências Práticas Quando a entrada aumenta em 100 ou 100.000 vezes, o que acontece com o algoritmo? Uma complexidade de solução incrivelmente complexa pode desmoronar com um conjunto de dados maior. Um algoritmo que parece bom para pequenos conjuntos de dados pode falhar drasticamente com os maiores, levando a problemas de desempenho e outros desafios. Aprendendo a pensar no abstrato Desenvolver a capacidade de pensar abstratamente sobre os problemas requer prática e orientação. Algumas estratégias incluem: : Representando problemas de forma generalizada. Criando modelos abstratos : avaliar como o algoritmo se comporta, independentemente de pontos de dados específicos. Analisar algoritmos separadamente dos dados : imaginando como o algoritmo funcionará com tamanhos variados de entrada. Construindo cenários de dimensionamento O pensamento abstrato em geral, e a notação Big O especificamente, são habilidades essenciais no projeto de algoritmos — em outras palavras, encontrar uma solução para um problema. Ao aprender a separar a complexidade da complexidade , os desenvolvedores podem evitar armadilhas comuns e aprimorar suas habilidades de resolução de problemas ao trabalhar sozinhos E aprimorar drasticamente a capacidade de trabalhar em conjunto com outras pessoas que investiram tempo semelhante para aprender a se comunicar dessa maneira. do problema do algoritmo complexos geralmente não exigem complexas. (Sally provavelmente não precisava de 37 melancias para começar... o que ela vai fazer com 37 melancias?!) Problemas soluções
