Pra que saber disso?

É importante saber analisar o tempo de execução de um algoritmo? As vezes sim.

Na vida do dev mediano, normalmente você vai estar fazendo CRUD em algum banco relacional, que já é bem eficiente nessa tarefa de organizar e buscar dados de maneira eficiente (óbvio, se você criar os índices, estruturar suas tabelas de forma adequada, e tudo mais).

Mas se você lida com sistemas maiores, onde um banco relacional normalmente não da conta do recado, ai você parte pra soluções NoSQL, onde você acaba tendo que, muitas vezes, escolher e utilizar da melhor forma a melhor estrutura de dados, pensar em como guardar e acessar esses dados, e ai saber fazer esse tipo de análise acaba se tornando muito mais importante.

É claro, são pouquíssimas empresas que atingem essa escala, tem muita gente usando soluções do Google e companhia só porque sim (ou sei lá por qual devaneio que passou pela cabeça da pessoa que tomou essa decisão), mas independente do motivo, tem gente cobrando isso em entrevista de emprego, então tá ai um ótimo motivo pra você estudar análise assintótica de algoritmos :)

Minha opinião sincerona é que tem muita empresa pedindo isso na entrevista (não só time complexity né, mas saber resolver probleminhas de lógica e estruturar uma solução usando as estruturas de dados e algoritmos mais eficientes) e não passando nem perto de ter escala e ser necessário utilizar essas soluções e tecnologias escaláveis para milhões e milhões de users, mas ai é assunto pra mesa de bar (ou pra um tweet que eu fiz algum tempo atrás, pode buscar na minha timeline, boa sorte :) hahaha).

Uma analogia

Sim, Cracking the code interview, sue me :)

Imagine o seguinte cenário, você precisa enviar um arquivo pra uma pessoa que mora lá longe, em outro país até, tipo o acre (brinks rsrs), e pra realizar essa tarefa existem algumas opções:

1 - enviar via internet (email, FTP, torrent rsrs, etc)

2 - copiar num HD e levar esse HD fisicamente (ou pen drive, ou qualquer coisa física)

Acho que todo mundo vai dizer que “aiiiwn mas é óbvio que enviar pela internet é muito mais fácil né”.

Mas e se o arquivo que você precisa enviar é realmente grande, tipo alguns petabytes?

Talvez o tempo de transferências de avião seja mais rápido do que via internet, e num cenário onde precisamos enviar da maneira mais rápido possível, talvez esta se torne uma opção viável.

Traduzindo este cenário para tempo de execução, enviar um arquivo via internet seria algo O(n), ou seja, o tempo cresce linearmente conforme o volume de dados fica maior (tamanho do arquivo). Enviar via avião seria O(1), que é constante, demora o mesmo tanto, independente do volume de dados.

Premissas para análise de algoritmos

Ao analisar algoritmos queremos mensurar, de alguma forma, os recursos gastos para execução de tal algoritmo. Esses recursos podem ser memória, largura de banda, consumo de energia, etc. Na maioria dos casos, entretanto, estamos interessados em analisar o tempo computacional, ou seja, o tempo em que ele demora para rodar.

Analisando o tempo de execução, conseguimos escolher o algoritmo mais eficiente para executar determina tarefa, ou seja, resolver determinado problema. Podem existir mais de um algoritmo viável, porem, nesse processo, definitivamente conseguimos cortar vários outros algoritmos que são inferiores.

As premissas que assumimos são as de que estaremos trabalhando com um único processador genérico, ou seja, nada de programas com concorrência, onde instruções são executadas uma após a outra, onde cada instrução leva o mesmo tempo para ser executada e que cada acesso a dados também leva esse mesmo tempo (acessando o valor de uma variável ou guardando um valor). Dado isto, conseguimos calcular de maneira grosseira o tempo de execução de um algoritmo pois estamos definindo as instruções necessárias ao processador e o tempo que cada uma leva pra executar. Um ponto que vale destacar é que não necessariamente precisamos definir todas as operações, pois elas podem ser derivadas de outras dado que as operações base estão definidas.
Se quiserem saber mais sobre este assunto procurem sobre RAM model (ou random access machine).

Melhor caso, pior caso e a média (ou caso esperado)

Ao analisarmos um algoritmo normalmente conseguimos dividir o tempo de execução em alguns casos diferentes, por exemplo, um algoritmo de ordenação qualquer (pega uma lista de objetos e ordena eles baseado em algum critério).

Fazendo a analise desse algoritmo, podemos supor pelo menos 3 casos:

Caso ideal

Nesse caso a lista já se encontra organizada e não precisamos fazer nada

Pior Caso

Aqui o algoritmo vai iterar sobre a lista quantas vezes forem necessárias para ordenarmos ela da melhor forma possível

Caso esperado

Aqui a lista já está de alguma forma ordenada e não necessariamente precisaremos ordenar iterar sobre todos os elementos da lista.

Dado esses cenários, ao analisarmos algoritmos, na maioria das vezes, estamos interessados no pior caso, e aqui vão 3 motivos:

1. O pior caso lhe dará uma estimativa do limite superior do tempo de execução, ou seja, voce consegue assumir que ele nunca sera pior do que aquilo, isso é muito importante pois conseguimos dimensionar nossas operações baseado nesse detalhe.
2. Para alguns algoritmos, o pior caso é o casos de maior ocorrência, ou seja, na grande parte do tempo ele vai estar no pior caso.
3. O caso esperado e o pior caso vão ser, na maioria das vezes, quase tão ruins quanto, ou seja, a diferença entre eles será mínima.

Ordem de grandeza do crescimento do tempo de execução

Ao fazer a analise de um algoritmo iremos nos deparar com funções diversas, por exemplo, um polinômio N^2 + N, nesses casos, para N grande o suficiente, o tempo gasto em N^2 sera significantemente maior do que em N, sendo assim, podemos desprezar N para descrever o tempo de execução.

Então, resumindo, estaremos sempre interessados na ordem de grandeza do crescimento do tempo de execução de um algoritmo, para expressar este tempo caracterizamos com uma letra maiúscula O e sua ordem de grandeza de crescimento pela letra n, ficando a notação assim O(n) (Lê-se O de n). Este é o famoso Big O em analise de algoritmos.

E assim concluímos a introdução ao Big O e sua definição, próximos posts vou detalhar mais como fazemos o calculo do Big O para diferentes algoritmos.

OBS: Já adianto que é uma decorebinha, normalmente você vai ver padrões nos algoritmos e vai conseguir identificar o Big O dali, mas sempre é possível calcular o tempo na mão, porém é necessário um ferramental matemático mais avançado as vezes, como álgebra, estatística, probabilidade, etc.