Complexidade de tempo de algoritmos
Já adianto, não sou nenhum profissional nem nada do gênero. É algo que estou estudando agora, assim como outras postagens que ainda pretendo fazer, a intenção é tentar explicar alguns conceitos, ideias, etc. com uma linguagem mais simples e reforçar o conhecimento na minha mente. Ao fim dos posts, deixarei algumas referências nas quais me baseei para aprender e escrever sobre.
Quando se pensa em formas de avaliar o desempenho de um algoritmo, a mais clara e fácil de se imaginar é a partir do tempo de execução (runtime), quanto tempo o algoritmo leva para ser executado completamente. Mas desta maneira não há como encontrar uma medição precisa de tempo, pois a linguagem de programação, hardware por completo, disponibilidade do hardware (se algum(ns) programa(s) - entre outros recursos que consomem do dispositivo - está(ão) sendo executado(s) no mesmo momento), quantidade de dados de entrada etc. levam a uma variação do tempo.
Por isso, uma maneira mais viável de analisar a eficiência de algoritmos foi identificar a complexidade de tempo dele, aí que entra a notação Big O, Omega e Theta. Essas notações são todas notações matemáticas baseadas em funções (lineares, logarítmicas, entre outras, basicamente, todas - ou quase - que são ensinadas no ensino básico) com o objetivo de encontrar a proporção(complexidade) em que a quantidade de etapas aumenta. Tempo e etapas são diretamente proporcionais.
Diferença entre as notações citadas:
Big O (O()): Mensura o pior caso possível de um algoritmo, a quantidade máxima de etapas nesta complexidade.
Big Omega (Ω()): Define a melhor situação possível de um algoritmo, a menor quantidade de etapas necessárias para fazer o que se quer nesta complexidade.
Big Theta (θ()): Descreve o ponto justo de quantidade de etapas de execução de um algoritmo.
Um exemplo bem simples de O e Ω: em um vetor existem 10 elementos, e dentre eles você quer achar algum específico. A melhor situação desse cenário (Big Ω) é o elemento que se busca estar na primeira posição, assim uma verificação é o suficiente. Já no pior, Big O, seria o elemento estar na última posição, será necessário realizar 10 verificações para então encontrar o elemento buscado.
Big O é o que mais importa, pois é muito melhor garantir que uma catástrofe não aconteça do que torcer para que ela não aconteça. A complexidade de tempo com Big O, normalmente é representada como: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n).
Assim é mais prático para se ter uma noção da demora de execução de um código, identificar o tipo de função que a notação pertence (logarítmica, constante além de outros) ao invés de montar e analisar uma função inteira. Por trás dos panos, o que está entre os parênteses de O são funções completas.
Este post está restringido a uma questão mais teórica e sem muitos exemplos, em breve, buscarei fazer uma publicação sobre cada tipo de complexidade, analisando gráfico e código.
Aceito sugestões e correções. Gostaria de saber o que acharam da explicação também,se possível.
Deus abençoe.
REFERÊNCIAS
Livro "Cientista da computação Autodidata", Cory Althoff, Capitulo 1: "O que é um algoritmo ?"
https://oieduardorabelo.medium.com/os-fundamentos-da-nota%C3%A7%C3%A3o-big-o-2360d4778803
https://joaoarthurbm.github.io/eda/posts/analise-assintotica/