Executando verificação de segurança...
3

O que é BIG O?

É um conceito muito importante que a maioria das big techs estão usando.
É útil ter uma ideia de quanto tempo o computador executará um programa.

Vemos que com o aumento do número de operações, pior será o programa. E se fizermos apenas uma operação para resolver o problema, será excelente.
Isso acontece porque, com mais operações em execução, mais sua CPU trabalhará e também consumirá muito mais da sua memória.

Carregando publicação patrocinada...
3

A notação big O, o O-zão, foi criada para resolver o problema da comparação de algoritmos.

O problema da comparação

Como eu faço pra medir se o meu programa é mais rápido (ou mais eficiente em uso de memória) que o programa do meu colega? Podemos rodar os dois programas várias vezes, com entradas cada vz maiores, medir quanto tempo gasta (se a variável que queremos medir é o tempo de execução), e fazer uma média. Mas e se o compilador mudar? E se quisermos comparar programas independentemente do computador? E se quisermos medir a eficiência intrínseca do algoritmo?

Para isso foram inventadas as notações assintóticas: big-Omega, big-Theta e big-O: limite inferior, limite superior e os dois ao mesmo tempo. Essas notações assintóticas descrevem como os algoritmos se composrtam com entradas cada vez maiores, ou seja, respondem à pergunta quando n tende ao infinito, qual o limite inferior do tempo (demora, pelo menos, quanto tempo pra rodar): Ω(n) (omega de n). Da mesma forma, "demora no máximo quanto tempo pra rodar": Θ(n) (theta de n). Por fim, "na média demora quanto?", ou "qual o limite superior e inferior?": O(n).

Qual a aplicação prática disso?

Saber disso te ajuda a entender porque um método que você usou é pior ou melhor que outro. Te ajuda a comparar duas ferramentas. O simples fato de ter estudado como determinar a complexidade de um algoritmo pode te dar a intuição de que "talvez essa não seja a melhor forma de fazer isso 🤔".

Muita gente acha inútil estudar algumas matérias como essa na faculdade, mas são essas matérias que te dão a base para as abstrações que são necessárias no trabalho. E se você não ficou convencido, dou o útlimo algumento: esse tipo de questão cai muito em entrevistas (questões de Estrutura de Dados e Análise de Algoritmos caem muito, no geral). E se os recrutadores esperam que gente saiba é porque algo de importante deve ter.

1

A notação big-o é muito mais antiga que a computação e qualquer problema de algoritmos. Ela serve pra análises assintóticas de crescimento de funções.

"In mathematics, it is commonly used to describe how closely a finite series approximates a given function, especially in the case of a truncated Taylor series or asymptotic expansion."

1

O trio Omega, Theta e Big-O foi proposto por Donald Knuth. Verdade que a notação omega e big-O é bem mais antiga (datando do final do século dezenove), mas o trio e a definição utilizada atualmente em computação é algo bem mais novo:

"the 1970s the big O was popularized in computer science by Donald Knuth, who introduced the related Theta notation, and proposed a different definition for the Omega notation."

1

Muito legal a resposta de rafaelbarbosas, complementando o seguinte ponto:

Vemos que com o aumento do número de operações, pior será o programa.

As notações assintóticas(big-O e outras) não tem o intuíto de definir quantas operações um algoritmo executa, e sim uma estimativa do número de operações executadas que dependem do tamanha da entrada.

Por exemplo, se tenho um algorítmo A que executa sempre 100 operações ele é categorizado como O(1)(tempo constante), pois independe do tamanho da entrada, sempre é executado 100 operações.

Da mesma forma que um algorítmo B pode executar uma operação para cada elemento de um vector de entrada, nesse caso depende da entrada, e é categorizado como O(n)(tempo linear).

Na análise assintótica, consideramos o algorítmo A mais rápido, no entanto, ele ainda sim pode executar mais operações que um algorítmo B(no caso onde a entrada de B é pequena).

Em outras palavras, a análise assintótica não preocupa-se somente com a quantidade total de operações, mas sim com o crescimento desse valor ao aumentar a entrada, que é o caso onde B executa mais operações.

1

é um conceito realmente interessante quando se fala de arquitetura de algoritmo, eu acabei estudando esse conceito no período de faculdade (ciência da computação), mais o uso se torna mais relevante quando se vai pra área da pesquisa científica, no dia a dia e difícil de se utilizar, mais quando se vai pra área de otimização de algoritmos o impacto é bem relevante.