Análise da Complexidade de Algoritmos

Ao trabalhar com algoritmos, é comum que se encontre problemas ou gargalos de eficiência à medida que ele escala em tamanho ou complexidade. Entender a complexidade do algoritmo que se está criando ou aplicando é fundamental para planejar o trabalho com qualidade e estabilidade.

Apesar de ser um tema comum nos cursos superiores em Ciência da Computação, muitos desenvolvedores carecem de conhecimentos em Análise de Complexidade de Algoritmos.

Mas esse assunto não precisa ser motivo de estresse. Confira este artigo aprofundado e entenda melhor os fatores que tornam um algoritmo simples ou complexo.

Como tornar seu algoritmo mais escalável que as tretas do Twitter?

Algum tempo após começar a programar, há um momento em que se tem aquele “clique”. Você começa a pensar nos problemas do ponto de vista de um programador. Não tem mais volta: você estará eternamente fadado a olhar para um interruptor e pensar:

Parece que o cérebro funciona com uma lógica booleana, mas não é isso. Você levou um bom tempo para que, em determinado momento, pudesse olhar para as coisas dessa forma. Isso é resultado de muito esforço, e ao mesmo tempo parece um “clique” porque não percebemos a nós mesmos com muita clareza.

Um desses “cliques” é o momento em que você deixa de pensar “Como posso resolver isso?” para pensar “Já sei como resolver, mas essa solução é suficiente?” ou “a solução é escalável ou legível?”.

Quando iniciantes, até conseguimos resolver problemas. Mas todo desafio proposto parece complicado, e nossa única preocupação é resolver da forma que for possível.

Isso muda conforme ganhamos experiência na solução de problemas. Agora, levamos menos tempo e temos o privilégio de pensar em uma implementação diferente.

Uma solução não-escalável é perfeitamente aceitável quando proposta ou encontrada por um iniciante. Ninguém deve cobrar de um estagiário, por exemplo,  desenvolvimento de soluções sofisticadas ou escaláveis. Tampouco se deve encarregá-lo de pontos críticos de um sistema.

Não ter conhecimentos profundos em Algoritmos e Estrutura de Dados não torna ninguém um mau programador, mas estes conhecimentos certamente proporcionam um daqueles “cliques” que mencionamos.

Complexidade de Algoritmos

A complexidade de um algoritmo é analisada em termos de tempo e espaço. Normalmente, o algoritmo terá um desempenho diferente com base no processador, disco, memória e outros parâmetros de hardware. A complexidade é usada para medir a velocidade de um algoritmo. Sendo o algoritmo um agrupamento de etapas para se executar uma tarefa, o tempo que leva para um algoritmo ser executado é baseado no número de passos. Digamos que um algoritmo percorre um array de dez posições somando o índice das posições a 200. A complexidade seria de 10x^t, sendo que ^t representa o tempo necessário para atualizar cada elemento do array com a operação de soma. Cada computador pode ser muito diferente: o tempo varia de acordo com o hardware, a linguagem utilizada e o sistema operacional.

Output:

Temos 10 operações acontecendo, aparentemente muito simples. Com uma Notação é possível calcular a complexidade de um algoritmo sem precisar levar em consideração parâmetros de hardware.

Big O Notation

A Big O Notation é uma notação especial que indica a complexidade de um algoritmo. Na realidade, existem várias notações: big e small O, big e small omega e theta.

A notação do O é sobre um “limite por cima”; a omega, “limite por baixo”; e a theta é a combinação de ambos. ‘Small’ Notations representam afirmações mais rígidas sobre a complexidade do que ‘Big’ Notations.

Geralmente a Big O é mais utilizada porque o interesse está em verificar, sem tanta rigidez, o máximo de recursos que o algoritmo vai utilizar, e tentar reduzir isso quando possível.

A função de tempo T(n) representa a complexidade do algoritmo, tal que T(n) = O(n) afirmando que um algoritmo tem uma complexidade linear de tempo, pois o TEMPO é relacionado a N, isto é, o tamanho de input do algoritmo.

Boa parte do material relacionado a Big O Notation é excessivamente formal. Isso talvez cause certo receio em algumas pessoas. Apesar disso, com alguma dedicação se torna fácil enxergar os padrões.

Em Big O Notation as complexidades de tempo linear, logarítmica, cúbica e quadrática são representações de complexidades diferentes de relação entre T e N em um algoritmo. A Big O Notation também é usada para determinar quanto espaço é consumido pelo algoritmo.

Você pode visualizar de forma gráfica o crescimento de tempo e de tamanho do input e como eles se relacionam. No final, é sobre isso: a relação entre um ou mais aspectos da entrada e o tempo de execução do algoritmo.

Importante: nem sempre o desempenho do algoritmo é afetado apenas pelo tamanho da entrada. O algoritmo de ordenação counting sort, por exemplo, é afetado também pelo maior número na lista.  

Começaremos pelas principais funções de complexidade, com ênfase na complexidade de tempo. Ao longo da explicação, assuntos como recursão serão explicados conforme necessário.

Finalmente, abordemos a questão que trouxe você até aqui: como calcular a complexidade de um algoritmo?

Constantes O(1)

Fazemos isso contando as diferentes operações. Observe o exemplo:

Aqui, temos uma multiplicação, uma adição e uma divisão – três operações. Não importa se N é igual a 2 ou 1 bilhão, o número de operações é o mesmo: três. Essa é uma complexidade de O(3). Isto é o que se chama de complexidade constante, pois o número de operações não muda – mesmo quando o input varia.

Mas a notação Big O tem regras que tornam dispensável que você fique somando cada operação. O(3) ou O(200), no final o tempo constante é sempre O(1).

Ademais, as constantes de um algoritmo são normalmente ignoradas. Isto porque a notação Big O se importa com o comportamento do algoritmo à medida que a entrada cresce, e não com os detalhes exatos para cada tamanho.

Quanto maior a entrada fica, menos importantes se tornam as constantes. Por isso, todo algoritmo com número de operações constante tem tempo de execução O(1) .

Esse gráfico demonstra como uma complexidade constante se comporta. No eixo vertical, temos a relação de tempo; no horizontal, a de N (input).

Na extremidade direita do eixo horizontal, temos um input de 10 TB sobre o algoritmo. Nessa simulação. ele gasta menos de um milésimo de execução. Mais à frente, analisaremos o mesmo gráfico em perspectiva a diferentes complexidades.

Complexidade Linear O(n)

Toda complexidade diferente da constante se dá em relação ao número de itens que a sua função recebe. Logo, quanto maior o input, maior o tempo de execução do algoritmo.

Apesar disso, na complexidade linear a diferença é bem proporcional ao tamanho da entrada, em vez de ser gritante. Em Big O Notation, complexidade linear é apresentada como O(n).

Algoritmos de String Matching, como Boyer-Moore (usando a regra de Galil) e Ukkonen têm complexidade linear.

Mas a proposta não é pegar algoritmos conhecidos e procurar no Google a complexidade deles. O objetivo é que você enxergue os padrões nesses algoritmos, e entenda-os a ponto de flagrar a complexidade no seu código e no de outras pessoas.

A pergunta a ser feita não é “esse algoritmo é O(n)?”, mas sim “por que esse algoritmo é O(n)?”. Se ao final desta leitura você puder responder a essa última pergunta, você está começando a entender Big O Notation.

A complexidade linear O(n) é demonstrada em um algoritmo da seguinte forma:

Aqui temos uma operação apenas – e não três, como anteriormente. Nesse caso, é total ++, que é o mesmo que: total é igual a total + 1. Porém, a complexidade é diferente, pois o input também define quantas vezes i será incrementado no for statement.

Então quanto maior for o input_(n)_ maior o número de operações que serão feitas em total.

Se no lugar de (i <= n), colocássemos (i <= 10) teríamos um tempo constante O(1). Mas como o input interfere no for, essa complexidade é O(n).

Ao analisar cada pedaço do código para encontrar o número de operações:

• total := 0 (Uma operação)
• i := 0 (Uma operação)
• i++(N operações)
• total ++(N operações)

Para analisar a complexidade do algoritmo não é necessário contar todas as operações. Na maioria das vezes, você vai acabar percebendo de forma intuitiva.

Nesse caso, como temos operações relacionadas a N (que é o número de inputs), não há por que se preocupar com as que são constantes. Isso pois a parte linear já dominará a notação de complexidade, então se deixarmos de lado as constantes sobram apenas as O(n).

E se você tiver dois for statement? 

Ainda assim, a complexidade será O(n) e não O(2n), porque Big O é sobre o comportamento quando a entrada cresce muito. Quanto maior fica a entrada, menos importa se é n ou 2n.

Agora temos em perspectiva dois tipos de complexidade: a constante, em cinza, e a linear, em azul. Agora fica muito óbvio o porquê do nome.

Repare que, desta vez, o input é de 10 GB, e não 10 TB. Usar um input de 10 TB em um algoritmo de complexidade O(n) consumiria bem mais tempo de execução.

A linha de O(1) permanece plana – leva menos de 1 segundo de runtime. A azul, com um input de 10 GB, leva 18 segundos.

Ainda que o objetivo não seja comparar tempos de execução, sua diferença para cada input é bastante expressiva.

Complexidade Logarítmica O(log n) 

É necessário entender um pouco sobre logaritmos para entender a próxima notação. Basicamente, o que você precisa ter em mente é que logaritmos são o inverso de exponenciais.

Se você está estudando por conta própria e acha que saber sobre complexidade e estrutura de dados não vai fazer diferença, tome cuidado!

Busque compensar estas lacunas pois, quando você fizer um teste, possivelmente alguém que faz ciências da computação vai disputar a vaga com você. E esta pessoa já conhece isso por padrão.

Isso é um logaritmo:

log2(8) = 3

Lê-se: log na base 2 de 8 é igual a 3. E porque é igual a 3? Porque a pergunta desse logaritmo é:

“a qual potência o número 2 deve ser elevado para resultar em 8?”

A resposta será 3, pois:

2³ = 2 * 2 * 2 

e

2 * 2 * 2 = 8

Voltando aos algoritmos, através do logaritmo de N podemos encontrar o número de operações realizadas durante o runtime:

log 2(n) = x 

Infelizmente nem tudo são flores, e nem todo logaritmo é na base de 2. Mas esse cálculo não é a parte mais importante. Repare que, até agora, falamos sobre as complexidades que têm exemplos matemáticos, como a exponenciação, mas não fizemos cálculos para chegar à notação do algoritmo.

Então, para uma lista de 8 números, você teria que verificar 3 números no máximo.

Para uma lista de 1.024 elementos:

log 1.024 = 10

porque

2¹⁰ = 1.024.

Então, para uma lista de 1.024 números, você tem que verificar 10 números no máximo.

Um exemplo de algoritmo com complexidade O(log n) é uma busca binária em uma lista já ordenada.

Esse tipo de algoritmo é bem simples: você parte o input ao meio e compara para verificar se o item a ser buscado é menor ou maior que o item no meio do array. Quando isso acontece, você descarta metade da lista – ficando com uma parte menor.

Esse processo é repetido até que se encontre o item da busca, diminuindo cada vez mais o processamento. Por isso ele é o inverso do exponencial: você diminui o N toda vez que um processamento é feito.

No exemplo do gráfico é possível observar que o número varia muito, porém o tempo é irrelevante em relação a outras complexidades. O input de 1 PB tem um tempo de execução de 3 milésimos de segundo.

O gŕafico mostra como N aumenta e, logo em seguida, se torna quase uma constante. Isso acontece porque, mesmo que N duplique, o algoritmo estará fatiando N pela metade repetidas vezes, até que encontre o resultado.

Esse exemplo da busca binária só funciona quando se tem uma lista ordenada. Caso contrário, o algoritmo não poderia garantir que o elemento procurado está de fato em uma metade ou outra da lista, sendo necessária outra abordagem.

Complexidade Quadrática O(N²)

Acabamos de falar sobre um caso em que se tem dois for e a complexidade é O(n). Mas esse caso é diferente, pois o for é aninhado; não é como se fosse um caso de N*2, mas sim N². Se N fosse 10, o retorno seria 100. A estas proporções, o tempo de execução é muito maior.

Enquanto a complexidade linear sobe em uma linha reta, a complexidade quadrática desenha uma curva (parábola) em relação ao eixo de tempo para cada vez que N aumenta.

Nesse caso, a regra de pensar quem domina quem também é válida. Se você tiver dois for aninhados e um solto dentro da função, você não tem um O(n + n²) porque o N linear é insignificante perto do quanto N² cresce. Então, no final, conte apenas com a maior função: O(n²). 

Até certo ponto, um algoritmo linear pode ser pior que um quadrático – justamente por causa das constantes. Em algum momento o quadrático vai ficar mais lento, mas e se isso só acontecer quando a entrada tiver mais de 500 terabytes? Vale a pena usar o linear?

Não se preocupe: para algoritmos simples e na maior parte dos casos de uso no mercado de software, o ponto onde o O(n²) fica mais lento é bem cedo.

Output:

Com um parâmetro de 2, esse seria o output, porque o índice i varia de 0 a n para cada um dos valores de j. O número de cálculos vai ser uma multiplicação deles, em vez da soma. Ou seja, muito mais passos para parâmetros maiores.

Há ainda a Complexidade Cúbica O(n³) – três loops aninhados – e a lógica é a mesma, mas não abordaremos o tema neste texto. Para exemplificar, entretanto:

Temos três loops percorrendo um array multidimensional. A complexidade aumenta tanto que, para percorrer esse array com três loops, são necessárias mil operações (pois 10 x 10 x 10 = 1000). Se o tamanho do array aumenta, também cresce o número de operações.

Agora é possível ter uma ideia da perspectiva. Veja como a linha vermelha de uma complexidade quadrática sobre em relação às outras. Note também como a complexidade linear parece plana em relação à quadrática.

Aqueles 18 segundos parecem um instante quando comparados aos mais de 60 segundos com um input de meros 10kb. 

Se tivermos no mesmo algoritmo essas três complexidades, pouco importa se o O(n) vai receber 1 TB de input. Nesse caso, o “problema” é essa O(n³).

Por isso nos preocupamos apenas com a maior função em relação a Big O Notation. É aquela que domina as outras à medida que a entrada cresce, e

as faz parecerem insignificantes.

Algumas ideias para calcular operações com Big O

• Operações aritméticas são sempre constant time (os algoritmos de aritmética em si não são, mas nós consideramos que sim);
• Atribuições de variáveis são constant time;
• Acessar elementos de array por index ou objetos por chave é constant time, enquanto acessar elementos de linked lists (como em Python) é linear time;
• Em um loop, a complexidade é o tamanho do loop * a complexidade do que estiver dentro do loop.

As complexidades quadrática e cúbica são chamadas de polinomiais. Todo algoritmo com complexidade n elevado a uma constante (2, 3, 4, 5, 6, etc) é polinomial. Se o algoritmo tiver complexidade n elevada a alguma variável que também cresce com a entrada (por exemplo, uma força bruta para o algoritmo do caixeiro-viajante ou quebrar senhas), então o algoritmo é exponencial, a pior e mais lenta das complexidades.

Se esta leitura foi construtiva para o seu desenvolvimento profissional, compartilhe-a com seus amigos e colegas!