Notação Big O: o que é e por que é importante?

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 objetivo do Big O Notation é poder falar, literalmente se comunicar com outras pessoas , sobre uma qualidade de nosso ofício. O foco particular aqui é permitir a comparação entre soluções no pior cenário à medida que o tamanho da entrada aumenta.

Queremos poder falar sobre soluções potenciais (o mesmo que dizer: algoritmos ) de forma abstrata. Este é um ponto crucial: em abstrato . Não nos importamos , de forma alguma , com os dados que temos . Quando brincamos com essas ideias, assumimos um conjunto de dados teoricamente gigantesco, mas finito.

Quando pensamos nos dados que temos , 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.

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:

• Criando modelos abstratos : Representando problemas de forma generalizada.

• Analisar algoritmos separadamente dos dados : avaliar como o algoritmo se comporta, independentemente de pontos de dados específicos.

• Construindo cenários de dimensionamento : imaginando como o algoritmo funcionará com tamanhos variados de entrada.

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 do problema da complexidade do algoritmo , 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.

Problemas complexos geralmente não exigem soluções complexas. (Sally provavelmente não precisava de 37 melancias para começar... o que ela vai fazer com 37 melancias?!)